[LeetCode] Problem 106 - Construct Binary Tree from Inorder and Postorder Traversal

Posted on | In ,

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

Note

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

For example, given

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

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[] inorder, int[] postorder) {
    return helper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
}

private TreeNode helper(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd) {
    if (inStart > inEnd || postStart > postEnd)
        return null;

    int i = inStart;

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

    TreeNode root = new TreeNode(postorder[postEnd]);
    root.left = helper(inorder, postorder, inStart, i - 1, postStart, postEnd - inEnd + i - 1);
    root.right = helper(inorder, postorder, i + 1, inEnd, postEnd - inEnd + i, postEnd - 1);

    return root;
}