105. 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.

Solution:

The first element in preorder array is the root of the tree.

We can use this value to find its index in inorder array.

When we find the root in inorder array, we know the left part of inorder array is its left subtree and the right part of inorder array is its right subtree.



Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length != inorder.length) {
            return null;
        }
        return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    
    public TreeNode helper(int[] preorder, int preLo, int preHi, int[] inorder, int inLo, int inHi) {
        if (preLo > preHi || inLo > inHi) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preLo]);
        
        int inRoot = inLo;
        for (int i = inLo; i <= inHi; i++) {
            if (inorder[i] == root.val) {
                inRoot = i;
            }
        }
        
        int leftLen = inRoot - inLo;
        root.left = helper(preorder, preLo + 1, preLo + leftLen, inorder, inLo, inRoot - 1);
        root.right = helper(preorder, preLo + leftLen + 1, preHi, inorder, inRoot + 1, inHi);
        return root;
    }
}