# 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;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://howardyangemail.gitbook.io/decode-leetcode/tree/construst-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.