Skip to content

889. Construct Binary Tree from Preorder and Postorder Traversal 👍

  • Time: $O(n)$
  • Space: $O(n)$
 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
26
27
28
29
30
31
32
33
class Solution {
 public:
  TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
    unordered_map<int, int> postToIndex;

    for (int i = 0; i < post.size(); ++i)
      postToIndex[post[i]] = i;

    return build(pre, 0, pre.size() - 1, post, 0, post.size() - 1, postToIndex);
  }

 private:
  TreeNode* build(const vector<int>& pre, int preStart, int preEnd,
                  const vector<int>& post, int postStart, int postEnd,
                  const unordered_map<int, int>& postToIndex) {
    if (preStart > preEnd)
      return nullptr;
    if (preStart == preEnd)
      return new TreeNode(pre[preStart]);

    const int rootVal = pre[preStart];
    const int leftRootVal = pre[preStart + 1];
    const int leftRootPostIndex = postToIndex.at(leftRootVal);
    const int leftSize = leftRootPostIndex - postStart + 1;

    TreeNode* root = new TreeNode(rootVal);
    root->left = build(pre, preStart + 1, preStart + leftSize, post, postStart,
                       leftRootPostIndex, postToIndex);
    root->right = build(pre, preStart + leftSize + 1, preEnd, post,
                        leftRootPostIndex + 1, postEnd - 1, postToIndex);
    return root;
  }
};

 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
26
27
28
29
30
class Solution {
  public TreeNode constructFromPrePost(int[] pre, int[] post) {
    Map<Integer, Integer> postToIndex = new HashMap<>();

    for (int i = 0; i < post.length; ++i)
      postToIndex.put(post[i], i);

    return build(pre, 0, pre.length - 1, post, 0, post.length - 1, postToIndex);
  }

  private TreeNode build(int[] pre, int preStart, int preEnd, int[] post, int postStart,
                         int postEnd, Map<Integer, Integer> postToIndex) {
    if (preStart > preEnd)
      return null;
    if (preStart == preEnd)
      return new TreeNode(pre[preStart]);

    final int rootVal = pre[preStart];
    final int leftRootVal = pre[preStart + 1];
    final int leftRootPostIndex = postToIndex.get(leftRootVal);
    final int leftSize = leftRootPostIndex - postStart + 1;

    TreeNode root = new TreeNode(rootVal);
    root.left = build(pre, preStart + 1, preStart + leftSize, post, postStart, leftRootPostIndex,
                      postToIndex);
    root.right = build(pre, preStart + leftSize + 1, preEnd, post, leftRootPostIndex + 1,
                       postEnd - 1, postToIndex);
    return root;
  }
}

 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
26
27
class Solution:
  def constructFromPrePost(
      self,
      pre: list[int],
      post: list[int],
  ) -> TreeNode | None:
    postToIndex = {num: i for i, num in enumerate(post)}

    def build(preStart: int, preEnd: int, postStart: int, postEnd: int) -> TreeNode | None:
      if preStart > preEnd:
        return None
      if preStart == preEnd:
        return TreeNode(pre[preStart])

      rootVal = pre[preStart]
      leftRootVal = pre[preStart + 1]
      leftRootPostIndex = postToIndex[leftRootVal]
      leftSize = leftRootPostIndex - postStart + 1

      root = TreeNode(rootVal)
      root.left = build(preStart + 1, preStart + leftSize,
                        postStart, leftRootPostIndex)
      root.right = build(preStart + leftSize + 1, preEnd,
                         leftRootPostIndex + 1, postEnd - 1)
      return root

    return build(0, len(pre) - 1, 0, len(post) - 1)