[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal

Posted on | In

Problem

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

1
2
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

1
2
3
4
5
    3
   / \
  9  20
    /  \
   15   7

Explanation

  1. We know that in the preorder array, the first element is the root of the tree. We can find this value also in the inorder array. For example, preorder[] = {1, 2, 4, 3, 5}, and inorder[] = {4, 2, 1, 5, 3}, and the tree is illustrated below:

    1
    2
    3
    4
    5
             1
        / \
       2   3
      /   /
     4   5

  2. From the above illustration, we see that the root node 1 is the first value of preorder, and we can find it in the inorder array at the third element. So, in the inorder array, any elements before 1 is from the left subtree, which are 4 and 2, and so in the preorder array, its next two elements 2 and 4 are from the left subtree too; in the inorder array, any elements after 1 is from the right subtree, which are 5 and 3, and so in the preorder array, its next two elements 3 and 5 are from the right subtree too.

  3. We can construct the left subtree and right subtree and connect it with the root node and we are done. Now, how do we construct the left and right subtree. We can do using the recursion method and create 3 variables to record the subtree’s inorder and preorder array’s range: preStart to record the start index of the preorder array, inStart and inEnd to record the start and ending index of the inorder array. We don’t need preEnd because both array should have the same length.

  4. Initially, preStart is 1, inStart is 4, inEnd is 3. Now, the left subtree’s preStart is 2, inStart is 4 and inEnd is 2; the right subtree’s preStart is also 2, inStart is 5, inEnd is 3. We can recursivly using the above method to find out the range of left and right subtree, and connect it with the root recursivly.

  5. The base case is preStart is greater than preorder’s length and inStart is greater than inEnd.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode helper(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {
        if (preStart >= preorder.length || inStart > inEnd) return null;
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        int i = inStart;
        while (i <= inEnd) {
            if (inorder[i] == rootVal) break;
            i++;
        }
        root.left = helper(preorder, inorder, preStart+1, inStart, i-1);
        root.right = helper(preorder, inorder, preStart+(i-inStart+1), i+1, inEnd);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length == 0 || preorder.length != inorder.length) return null;
        return helper(preorder, inorder, 0, 0, inorder.length-1);
    }
}