Leetcode: 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.

Understand the problem:

The problem gives two arrays, which represent the preorder and inorder traversal of the binary tree. Construct the binary tree according to the two traversals. 

We can use several examples to better understand the problem.  For a tree

              1

            /    \

          2     3

         /   \

       4     5

The preorder traversal is 1, 2, 4, 5, 3
The inorder traversal is 4, 2, 5, 1, 3

Solution:
The solution is based on the idea of preorder traversal. For a given arrays of preorder traversal and inorder traversal, the first node of the preorder array must be the root value, then we can divide the inorder array into two parts according to the value in the first node of the preorder traversal. The left part must be its left subtree, while the right part must be its right subtree. Then we divide the problem into smaller question, and repeat the above operations until there is only one node for each side.

Code (Java):

/**
 * Definition for binary tree
 * 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 == null || inorder == null || preorder.length == 0 || inorder.length == 0)
            return null;
        
        int len = preorder.length;
        
        return buildTree(preorder, 0, len - 1, inorder, 0, len - 1);
    }
    
    private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (inStart > inEnd) {
            return null;
        }
        
        int rootVal = preorder[preStart];
        int rootIdx = 0;
        
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIdx = i;
                break;
            }
        }
        int len = rootIdx - inStart;
        TreeNode root = new TreeNode(rootVal);
        
        // recursively call its left and right subtree
        root.left = buildTree(preorder, preStart + 1, preStart + len, inorder, inStart, rootIdx - 1);
        root.right = buildTree(preorder, preStart + len + 1, preEnd, inorder, rootIdx + 1, inEnd);
        
        return root;
    }
}

Summary:
This question is relatively tricky in Leetcode. The key idea is to partition the two lists into sublists, and recursively solve the problem. Be careful the recursive solutions in tree-based questions. It is extremely useful.