105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]
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[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length != inorder.length) {
return null;
}
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return recurse(preorder, 0, preorder.length - 1, inorder, 0, preorder.length - 1);
}
private TreeNode recurse(int[] preorder, int startPre, int endPre, int[] inorder, int startIn, int endIn) {
if (startPre > endPre || startIn > endIn) {
return null;
}
// Take in following example when working on boundary problems.
// pre order [x,9,20,15,7]
// in order [9,x,15,20,7]
// the first output node in post-order sequence is the root
int val = preorder[startPre];
TreeNode root = new TreeNode(val);
// midIn = 1
int midIn = inorderMap.get(val);
// midIn - startIn represents the length of left tree
// midPre = 0 + 1 - 0 = 1
int midPre = startPre + midIn - startIn;
// 1. For pre-order output, [startPre+1:midPre] are left nodes, [midPre+1:endPre] are the right nodes
// 2. For in-order output, [startIn+0:midIn-1] are left nodes, [midIn+1:endIn] are right nodes.
// pre order [1,1], inorder [0,0]
root.left = recurse(preorder, startPre + 1, midPre, inorder, startIn, midIn - 1);
// pre order [2,4], in order [2,4]
root.right = recurse(preorder, midPre + 1, endPre, inorder, midIn + 1, endIn);
return root;
}
}