106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
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:
3 / \ 9 20 / \ 15 7
Solutions
class Solution {
// Keep the index for specific node in inorder sequence which boosts up the efficiency
// of searching for split point.
Map<Integer, Integer> inorderMap = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || postorder == null || inorder.length != postorder.length) {
return null;
}
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return recurse(inorder, 0, inorder.length - 1, postorder, 0, inorder.length - 1);
}
private TreeNode recurse(int[] inorder, int startIn, int endIn, int[] postorder, int startPost, int endPost) {
if (startIn > endIn || startPost > endPost) {
return null;
}
// Take in following example when working on boundary problems.
// in order [9, x, 15, 20, 7]
// post order [9, 15, 7, 20, x]
// the last output node in post-order sequence is the root
int val = postorder[endPost];
TreeNode root = new TreeNode(val);
// midIn = 1
int midIn = inorderMap.get(val);
// midIn - startIn represents the length of left tree
// midPost = 0+1-0=1
int midPost = startPost + midIn - startIn;
// 1. For in-order output, [startIn:midIn-1] are left nodes, [midIn+1:endIn] are right nodes.
// 2. For post-order output, [startPost:midPost] are left nodes, [midPost+1:endPost - 1] are the right nodes
// in order [0,0], post order [0,0]
root.left = recurse(inorder, startIn, midIn - 1, postorder, startPost, midPost - 1);
// in order [2,4], post order [1, 3]
root.right = recurse(inorder, midIn + 1, endIn, postorder, midPost, endPost - 1);
return root;
}
}