[LeetCode] Problem 105 - Construct Binary Tree from Preorder and Inorder Traversal

Posted on | In ,

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

Note

You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public TreeNode buildTree(int[] preorder, int[] inorder) {
    return helper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}

private TreeNode helper(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd)
            return null;

    int i = inStart;

    for (; i <= inEnd; i++) {
            if (inorder[i] == preorder[preStart])
                    break;
    }

    TreeNode root = new TreeNode(preorder[preStart]);
    root.left = helper(preorder, inorder, preStart + 1, preStart + i - inStart, inStart, i - 1);
    root.right = helper(preorder, inorder, preStart + i - inStart + 1, preEnd, i + 1, inEnd);

    return root;
}