Construst Tree

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

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 Integer.MIN_VALUE and mid.val, root right as value in range mid.val and Integer.MAX_VALUE. Return null if exceed the range.

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

Use a StringBuilder to append elements from tree to string.

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,n,n,4,5]"
// 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;
}

Use BST characteristics to construct BST.

// 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;
}

Construct tree key and count the number of subtrees in the same pattern.

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

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.

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

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

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.

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

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

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

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

Maintain two ranges.

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

Last updated

Was this helpful?