[LeetCode] Problem 889 - Construct Binary Tree from Preorder and Postorder Traversal

Posted on | In ,

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]

Output: [1,2,3,4,5,6,7]

Note

  • 1 <= pre.length == post.length <= 30
  • pre[] and post[] are both permutations of 1, 2, …, pre.length.
  • It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

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
22
23
24
25
public TreeNode constructFromPrePost(int[] pre, int[] post) {
    return helper(pre, post, 0, pre.length - 1, 0, post.length - 1);
}

private TreeNode helper(int[] pre, int[] post, int preStart, int preEnd, int postStart, int postEnd) {
    if (preStart > preEnd)
        return null;

    TreeNode root = new TreeNode(pre[preStart]);

    if (preStart == preEnd)
        return root;

    int i = postEnd - 1;

    for (; i >= postStart; i--) {
        if (post[i] == pre[preStart + 1])
            break;
    }

    root.left = helper(pre, post, preStart + 1, preEnd - postEnd + i + 1, postStart, i);
    root.right = helper(pre, post, preEnd - postEnd + i + 2, preEnd, i + 1, postEnd - 1);

    return root;
}