> For the complete documentation index, see [llms.txt](https://howardyangemail.gitbook.io/decode-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://howardyangemail.gitbook.io/decode-leetcode/tree/construst-tree.md).

# Construst Tree

#### [108. Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/)

{% tabs %}
{% tab title="Java" %}

```java
public TreeNode sortedArrayToBST(int[] nums) {
    if (nums == null || nums.length == 0) return null;
    return helper(nums, 0, nums.length - 1);
}

private TreeNode helper(int[] nums, int left, int right) {
    if (left == right) return new TreeNode(nums[left]);
    if (left > right) return null;
    int mid = (right + left) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = helper(nums, left, mid - 1);
    root.right = helper(nums, mid + 1, right);
    return root;
    
}
```

{% endtab %}

{% tab title="Python" %}

```python
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums or len(nums) == 0:
            return None
        return self.helper(nums, 0, len(nums) - 1)
    
    def helper(self, nums, L , R):
        if L > R:
            return None
        if L == R:
            return TreeNode(nums[L])
        mid = L + (R - L) // 2
        curt = TreeNode(nums[mid])
        curt.left = self.helper(nums, L, mid - 1)
        curt.right = self.helper(nums, mid + 1, R)
        return curt
```

{% endtab %}
{% endtabs %}

#### [**109. Convert Sorted List to Binary Search Tree**](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/)

Use fast and slow pointer to find mid of the list. Construct root as the mid value. Recursively construct root left as value in range I`nteger.MIN_VALUE` and `mid.val`, root right as value in range `mid.val` and `Integer.MAX_VALUE`. Return null if exceed the range.

```java
public TreeNode sortedListToBST(ListNode head) {
    return buildTree(head, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private TreeNode buildTree(ListNode head, int min, int max) {
    ListNode mid = getMid(head);
    if (mid == null || mid.val <= min || mid.val >= max) return null;
    TreeNode root = new TreeNode(mid.val);
    root.left = buildTree(head, min, root.val);
    root.right = buildTree(mid.next, root.val, max);
    return root;
}

private ListNode getMid(ListNode head) {
    ListNode pre = new ListNode(-1);
    pre.next = head;
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        pre = slow;
        fast = fast.next.next;
        slow = slow.next;
    }
    pre.next = null;
    return slow;
}
```

#### [297. Serialize and Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/)

Use a StringBuilder to append elements from tree to string.&#x20;

```
    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,n,n,4,5]"
```

{% tabs %}
{% tab title="Java" %}

```java
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    if (root == null) return "";
    serializehelper(root, sb);
    return sb.toString();
}

private void serializehelper(TreeNode root, StringBuilder sb) {
    if (root == null) {
        sb.append(',').append("n");
        return;
    }
    if (sb.length() == 0) {
        sb.append(root.val);
    } else {
        sb.append(",").append(root.val);
    }
    serializehelper(root.left, sb);
    serializehelper(root.right, sb);
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if (data.isEmpty()) return null;
    Queue<String> q = new LinkedList<>(Arrays.asList(data.split(",")));
    return deserialHelper(q);
}

private TreeNode deserialHelper(Queue<String> q) {
    if (q.isEmpty()) return null;
    String s = q.poll();
    if (s.equals("n")) return null;
    TreeNode curt = new TreeNode(Integer.valueOf(s));
    curt.left = deserialHelper(q);
    curt.right = deserialHelper(q);
    return curt;
}
```

{% endtab %}

{% tab title="Java (can implement graph)" %}

```java
    // Encodes a tree to a single string.
    StringBuilder sb = new StringBuilder();
    int id = 0;
    public String serialize(TreeNode root) {
        int rootId = serialHelper(root);
        return sb.toString();
    }
    
    private int serialHelper(TreeNode root) {
        if (root == null) return -1;
        id++;
        int curtId = id;
        int leftId = serialHelper(root.left);
        int rightId = serialHelper(root.right);
        sb.append(root.val).append(",");
        sb.append(curtId).append(",");
        sb.append(leftId).append(",");
        sb.append(rightId).append(";");
        return curtId;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nodes = data.split(";");
        Map<Integer, TreeNode> map = new HashMap<>();
        for (int i = 0; i < nodes.length; i++) {
            String[] nodedata = nodes[i].split(",");
            if (nodedata.length != 4) continue;
            int val = Integer.parseInt(nodedata[0]);
            int id = Integer.parseInt(nodedata[1]);
            int leftid = Integer.parseInt(nodedata[2]);
            int rightid = Integer.parseInt(nodedata[3]);
            if (!map.containsKey(id)) {
                TreeNode node = new TreeNode(val);
                map.put(id, node);
            } else {
                map.get(id).val = val;
            }
            if (!map.containsKey(leftid) && leftid != -1) {
                map.put(leftid, new TreeNode(-1));
            }
            if (!map.containsKey(rightid) && rightid != -1) {
                map.put(rightid, new TreeNode(-1));
            }
            map.get(id).left = map.get(leftid);
            map.get(id).right = map.get(rightid);
        }
        return map.get(1);
    }
```

{% endtab %}
{% endtabs %}

#### [449. Serialize and Deserialize BST](https://leetcode.com/problems/serialize-and-deserialize-bst/)

Use BST characteristics to construct BST.

```java
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    if (root != null) helper(sb, root);  
    return sb.toString();
}

private void helper(StringBuilder sb, TreeNode root) {
    sb.append(root.val);
    sb.append(",");
    if (root.left != null) helper(sb, root.left);
    if (root.right != null) helper(sb, root.right);
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if (data.isEmpty()) return null;
    String[] strs = data.split(",");
    Queue<String> q = new LinkedList<>(Arrays.asList(strs));
    return decode(q, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private TreeNode decode(Queue<String> q, int min, int max) {
    if (q.isEmpty()) {
        return null;
    }
    if (Integer.parseInt(q.peek()) < min || Integer.parseInt(q.peek()) > max) return null;
    int val = Integer.parseInt(q.poll());
    TreeNode root = new TreeNode(val);
    root.left = decode(q, min, val);
    root.right = decode(q, val, max);
    return root;
}
```

#### [652. Find Duplicate Subtrees](https://leetcode.com/problems/find-duplicate-subtrees/)

Construct tree key and count the number of subtrees in the same pattern.&#x20;

```java
List<TreeNode> res;
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    this.res = new ArrayList<>();
    Map<String, Integer> map = new HashMap<>();
    helper(root, map);
    return this.res;
}

private String helper(TreeNode root, Map<String, Integer> map) {
    if (root == null) {
        return "#";
    }
    String key = root.val + "," + helper(root.left, map) + "," + helper(root.right, map);
    map.put(key, map.getOrDefault(key, 0) + 1);
    if (map.get(key) == 2) {
        this.res.add(root);
    }
    return key;
}
```

#### [894. All Possible Full Binary Trees](https://leetcode.com/problems/all-possible-full-binary-trees/)

Break a big problem into several small problems. Get all possible combinations under N = 2 then construct the tree according to the combinations. Use memo.

```java
Map<Integer, List<TreeNode>> memo = new HashMap<>();
public List<TreeNode> allPossibleFBT(int N) {
    if (N <= 0 || N % 2 == 0) return new ArrayList<>();
    if (N == 1) {
        List<TreeNode> res = new ArrayList<>();
        res.add(new TreeNode(0));
        return res;
    } 
    if (memo.containsKey(N)) {
        return memo.get(N);
    }
    List<TreeNode> res = new ArrayList<>();
    for (int i = 1; i < N; i += 2) {
        List<TreeNode> leftSub = allPossibleFBT(i);
        List<TreeNode> rightSub = allPossibleFBT(N - i - 1);
        for (TreeNode l : leftSub) {
            for (TreeNode r : rightSub) {
                TreeNode root = new TreeNode(0);
                root.left = l;
                root.right = r;
                res.add(root);
            }
        }
    }
    memo.put(N, res);
    return res;
}
```

#### [1008. Construct Binary Search Tree from Preorder Traversal](https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/)

{% tabs %}
{% tab title="Java" %}

```java
int index = 0;
public TreeNode bstFromPreorder(int[] preorder) {
    return build(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private TreeNode build(int[] nums, int min, int max) {
    if (min > max) return null;
    if (index >= nums.length || nums[index] <= min || nums[index] >= max) {
        return null;
    }
    TreeNode root = new TreeNode(nums[index++]);
    root.left = build(nums, min, root.val);
    root.right = build(nums, root.val, max);
    return root;
}
```

{% endtab %}

{% tab title="Java (Iteration)" %}

```java
public TreeNode bstFromPreorder(int[] preorder) {
    int i = 0;
    TreeNode root = new TreeNode(preorder[i++]);
    Stack<TreeNode> stack = new Stack<>();
    stack.add(root);
    while (!stack.isEmpty() && i < preorder.length) {
        TreeNode newNode = new TreeNode(preorder[i]);
        if (preorder[i] > stack.peek().val) {
            TreeNode curt = null;
            while (!stack.isEmpty() && preorder[i] > stack.peek().val) {
                curt = stack.pop();
            }
            curt.right = newNode;
        } else {
            stack.peek().left = newNode;
        }
        stack.add(newNode);
        i++;
    }
    return root;
}
```

{% endtab %}
{% endtabs %}

#### [105. Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)

Use a pointer in `preorder` array to track the next number, also use a L and R boundary in `inorder` array to define the range. Make a `hashmap` to store the elements and its corresponding indicies.&#x20;

Get the index in inorder array, the left node is in inorder range between **inL and index - 1**, right node is between **index + 1 and inR**. In preorder, the next left node is i + 1, right is **i + size of left range + 1**, which is **i + inIndex - inLeft + 1**

```java
Map<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
    map = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }
    return helper(preorder, 0, inorder, 0, inorder.length - 1);
}

private TreeNode helper(int[] preorder, 
                       int index,
                       int[] inorder,
                       int inL,
                       int inR) {
    if (inL > inR || index >= preorder.length) {
        return null;
    }
    TreeNode root = new TreeNode(preorder[index]);
    int inIndex = map.get(root.val);
    root.left = helper(preorder, 
                       index + 1, 
                       inorder, 
                       inL, 
                       inIndex - 1);
    root.right = helper(preorder, 
                        index + inIndex - inL + 1,
                        inorder,
                        inIndex + 1,
                        inR);
    return root;
}
```

#### [106. Construct Binary Tree from Inorder and Postorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)

Similar as the question above. Postorder runs opposite as preorder.

```java
Map<Integer, Integer> inorderMap;
public TreeNode buildTree(int[] inorder, int[] postorder) {
    if (postorder == null || inorder == null 
        || postorder.length == 0 || inorder.length == 0) return null;
    inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) inorderMap.put(inorder[i], i);
    return build(postorder.length - 1, 0, inorder.length - 1, postorder);
}

private TreeNode build(int postIndex, int inLeft, int inRight, int[] postorder) {
    if (inLeft > inRight || postIndex >= postorder.length) return null;
    TreeNode root = new TreeNode(postorder[postIndex]);
    int inIndex = inorderMap.get(postorder[postIndex]);
    root.left = build(postIndex - (inRight - inIndex + 1), 
                        inLeft, 
                        inIndex - 1, 
                        postorder);
    root.right = build(postIndex - 1, 
                       inIndex + 1, 
                       inRight, 
                       postorder);
    return root;
}
```

#### [889. Construct Binary Tree from Preorder and Postorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)

&#x20;Maintain two ranges.

```java
Map<Integer, Integer> map;
public TreeNode constructFromPrePost(int[] pre, int[] post) {
    map = new HashMap<>();
    int n = pre.length;
    for (int i = 0 ; i < n; i++) {
        map.put(post[i], i);
    }
    return helper(pre, 0, n - 1, post, 0, n - 1);
}

private TreeNode helper(int[] pre, int preL, int preR, int[] post, int postL, int postR) {
    if (preL > preR || postL > postR) return null;
    TreeNode root = new TreeNode(pre[preL]);
    if (preL == preR) {
        return root;
    }
    int delta = map.get(pre[preL + 1]) - postL; 
    root.left = helper(pre,
                       preL + 1,
                       preL + delta + 1,
                       post,
                       postL,
                       postL + delta);
    root.right = helper(pre,
                        preL + 1 + delta + 1,
                        preR,
                        post,
                        postL + delta + 1,
                        postR - 1);
    return root;
}
```