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
Solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper(0, preorder.length - 1, 0, inorder.length - 1, preorder, inorder);
}
public TreeNode helper(int preStart, int preEnd, int inStart, int inEnd, int[] preorder, int[] inorder){
if (preStart > preEnd || inStart > inEnd){
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int inIndex = 0;
for (int i = inStart; i <= inEnd; i++){
if (inorder[i] == root.val){
inIndex = i;
}
}
root.left = helper(preStart + 1, preEnd, inStart, inIndex - 1, preorder, inorder);
root.right = helper(preStart + 1 + inIndex - inStart, preEnd, inIndex + 1, inEnd, preorder, inorder);
return root;
}
}
