Construct Binary Tree from Preorder and Postorder Traversal

LeetCode Q 889 - Construct Binary Tree from Preorder and Postorder Traversal

Return any binary tree that matches the given preorder and postorder traversals.
Values in the traversals pre and post are distinct positive integers.

Example 1:
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.

Solution:

Code:

Map<Integer, Integer> preIndexMap = new HashMap<>();
Map<Integer, Integer> postIndexMap = new HashMap<>();
    
public TreeNode constructFromPrePost(int[] pre, int[] post) {
  for (int i = 0; i < pre.length; i++) {
    preIndexMap.put(pre[i], i);
    postIndexMap.put(post[i], i);
  }

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

private TreeNode dfs(int[] pre, int[] post, int start, int end) {
  if (start > end) return null;
  if (start == end) return new TreeNode(pre[start]);

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

  int rightRootInPost = postIndexMap.get(pre[start]) - 1;
  int rightRootInPre = preIndexMap.get(post[rightRootInPost]);

  root.left = dfs(pre, post, start + 1, rightRootInPre - 1);
  root.right = dfs(pre, post, rightRootInPre, end);

  return root;
}