Question

link

Stats

Frequency	3
Difficulty	3
Adjusted Difficulty	3
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an interesting question.

The key is, the tree header is always the first element in the pre-order traversal. Knowing this is enough to help us divide the lists and solve the question recursively.

About time complexity. According to the analysis, it is O(nlgn) if the tree is balance, and O(n²) if the tree is totally skewed. This article suggests using HashTable for searching, which achieves O(n) efficiency.

We left out some details on how we search the root value’s index in the inorder sequence. How about a simple linear search? If we assume that the constructed binary tree is always balanced, then we can guarantee the run time complexity to be O(N log N), where N is the number of nodes. However, this is not necessarily the case and the constructed binary tree can be skewed to the left/right, which has the worst complexity of O(N2). I quote the entire article below.

A more efficient way is to eliminate the search by using an efficient look-up mechanism such as hash table. By hashing an element’s value to its corresponding index in the inorder sequence, we can do look-ups in constant time. Now, we need only O(N) time to construct the tree, which theoretically is the most efficient way.

Solution

I post my code below. However, a better code is written in this post.

Code

First, my code, it’s 100ms slower than next code.

public TreeNode buildTree(int[] preorder, int[] inorder) {
    int len = preorder.length;
    if (len == 0) return null;
    TreeNode root = new TreeNode(preorder[0]);
    int leftLen = 0;
    while (inorder[leftLen] != preorder[0]) leftLen++;
    int[] leftPreOrder = new int[leftLen];
    int[] rightPreOrder = new int[len - 1 - leftLen];
    int[] leftInOrder = new int[leftLen];
    int[] rightInOrder = new int[len - 1 - leftLen];
    for (int i = 1; i <= leftLen; i ++) {
        leftPreOrder[i-1] = preorder[i];
        leftInOrder[i-1] = inorder[i-1];
    }
    for (int i = leftLen + 1; i < len; i ++) {
        rightPreOrder[i-leftLen-1] = preorder[i];
        rightInOrder[i-leftLen-1] = inorder[i];
    }
    root.left = buildTree(leftPreOrder, leftInOrder);
    root.right = buildTree(rightPreOrder, rightInOrder);
    return root;
}

Second, other ppl’s code

public TreeNode buildTree(int[] preorder, int[] inorder) {
    int preLength = preorder.length;
    int inLength = inorder.length;
    return buildTree(preorder, 0, preLength - 1, inorder, 0, inLength - 1);
}

public TreeNode buildTree(int[] pre, int preStart, int preEnd, int[] in,
        int inStart, int inEnd) {
    if (inStart > inEnd) return null;
    int rootVal = pre[preStart];
    int rootIndex = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (in[i] == rootVal) {
            rootIndex = i;
            break;
        }
    }
    int len = rootIndex - inStart;
    TreeNode root = new TreeNode(rootVal);
    root.left = buildTree(pre, preStart + 1, preStart + len, in, inStart,
            rootIndex - 1);
    root.right = buildTree(pre, preStart + len + 1, preEnd, in,
            rootIndex + 1, inEnd);
    return root;
}