Construst Tree

108. Convert Sorted Array to Binary Search Tree

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

Python

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

297. Serialize and Deserialize Binary Tree

Use a StringBuilder to append elements from tree to string.

    1
   / \
  2   3
     / \
    4   5

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

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

Java (can implement graph)

449. Serialize and Deserialize BST

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

652. Find Duplicate Subtrees

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

894. 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.

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

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

Java (Iteration)

105. 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.

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

106. Construct Binary Tree from Inorder and Postorder Traversal

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

889. Construct Binary Tree from Preorder and Postorder Traversal

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