105. Construct Binary Tree from Preorder and Inorder Traversal

Leetcode Tree Depth-first Search

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:

分析¶

分析来源于这里。

对于上图的树来说，

index: 0 1 2 3 4 5 6
先序遍历为: 1 2 4 5 3 6 7
中序遍历为: 4 2 5 1 6 3 7

红色是根节点，蓝色为左子树，绿色为右子树。可以发现的规律是：

先序遍历的从左数第一个为整棵树的根节点。
中序遍历中根节点是左子树右子树的分割点。

再看这个树的左子树：

先序遍历为: 2 4 5
中序遍历为: 4 2 5

依然可以套用上面发现的规律。再看这个树的右子树：

先序遍历为: 3 6 7
中序遍历为: 6 3 7

也是可以套用上面的规律的。

所以这道题可以用递归的方法解决。

具体解决方法是：

通过先序遍历找到第一个点作为根节点，在中序遍历中找到根节点并记录index。
因为中序遍历中根节点左边为左子树，所以可以记录左子树的长度并在先序遍历中依据这个长度找到左子树的区间，用同样方法可以找到右子树的区间。
递归的建立左子树和右子树。

代码如下：

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) return null;
    if (preorder.length == 1) return new TreeNode(preorder[0]);
    //  通过先序遍历找到根节点
    int rootVal = preorder[0];
    // 在中序遍历中找到根节点并记录index
    int rootIndex = search(inorder, rootVal);
    // 建立根节点
    TreeNode root = new TreeNode(rootVal);
    // 建立左子树
    root.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + rootIndex),
            Arrays.copyOfRange(inorder, 0, rootIndex));
    //建立右子树
    root.right = buildTree(Arrays.copyOfRange(preorder, 1 + rootIndex, preorder.length),
            Arrays.copyOfRange(inorder, 1 + rootIndex, inorder.length));
    return root;
}

private int search(int[] inorder, int val) {
    for (int i = 0; i < inorder.length; i++) {
        if (inorder[i] == val) return i;
    }
    return -1;
}

上面反复使用了Arrays.copyOfRange()，大大增加了时间复杂度和空间复杂度。一个优化的方案是，给定数组的上边界和下边界。

public TreeNode buildTree(int[] preorder, int[] inorder) {
    return buildTreeHelper(preorder, 0, preorder.length,
            inorder, 0, inorder.length);

}

private TreeNode buildTreeHelper(int [] preorder, int preFrom, int preTo,
                                 int [] inorder, int inFrom, int inTo) {
    if (preTo <= preFrom) return null;
    //  通过先序遍历找到根节点
    int rootVal = preorder[preFrom];
    // 在中序遍历中找到根节点并记录index
    int rootIndex = -1;
    for (int i = inFrom; i < inTo; i++) {
        if (inorder[i] == rootVal) {
            rootIndex = i;
            break;
        }
    }
    // 左子树大小（节点个数）
    int leftTreeSize = rootIndex - inFrom;

    // 建立根节点
    TreeNode root = new TreeNode(rootVal);
    // 建立左子树
    root.left = buildTreeHelper(preorder, preFrom + 1, preFrom + 1 + leftTreeSize,
            inorder, inFrom, rootIndex);
    //建立右子树
    root.right = buildTreeHelper(preorder, preFrom + 1 + leftTreeSize, preTo,
            inorder, rootIndex + 1, inTo);
    return root;
}