Construct Binary Tree

Construct Binary Tree from Preorder and Inorder Traversal

• Time: O(n)
• Space: O(1)

Map<Integer, Integer> map = new HashMap<>();

public TreeNode buildTree(int[] pre, int[] in) {
    if (pre == null || pre.length == 0 || in == null || in.length == 0)
        return null;
    for (int i = 0; i < in.length; i++) {
        map.put(in[i], i);
    }
    return dfs(pre, 0, pre.length - 1, in, 0, in.length - 1);
}

private TreeNode dfs(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
    if (preStart > preEnd && inStart > inEnd) {
        return null;
    }
    TreeNode node = new TreeNode(pre[preStart]);
    int index = map.get(node.val);
    int size = index - inStart;
    node.left = dfs(pre, preStart + 1, preStart + size, in, inStart, index - 1);
    node.right = dfs(pre, preStart + size + 1, preEnd, in, inStart + size + 1, inEnd);
    return node;
}

Given inorder and postorder traversal of a tree, construct the binary tree.

• Time: O(n)
• Space: O(1)

Map<Integer, Integer> map = new HashMap<>();

public TreeNode buildTree(int[] in, int[] post) {
    if (in == null || in.length == 0 || post == null || post.length == 0)
        return null;
    for (int i = 0; i < in.length; i++) {
        map.put(in[i], i);
    }
    return dfs(in, 0, in.length - 1, post, 0, post.length - 1);
}

private TreeNode dfs(int[] in, int inStart, int inEnd, int[] post, int postStart, int postEnd) {
    if (postStart > postEnd && inStart > inEnd) {
        return null;
    }
    TreeNode node = new TreeNode(post[postEnd]);
    int index = map.get(node.val);
    int size = index - inStart;
    node.left = dfs(in, inStart, index - 1, post, postStart, postStart + size - 1);
    node.right = dfs(in, inStart + size + 1, inEnd, post, postStart + size, postEnd - 1);
    return node;
}