07 重建二叉树

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

解题思路：

先序遍历性质：节点按照 【根节点 | 左子树 | 右子树】排序。

中序遍历性质：节点按照 【左子树 | 根节点 | 右子树】排序。

根据以上性质，有以下结论：

1. 先序遍历的首个元素 $v$ 为根节点的值。

2. $v$ 在中序遍历中的位置，可以将中序遍历数组划分为左子树部分和右子树部分。

3. 根据结论 $2$ ，可以计算左子树的节点数，因此可以再将先序遍历划分为左子树部分和右子树部分。

根据以上结论，可以使用递归的方式对所有子树进行划分。

递归函数

递归参数：先序遍历数组 $preorder$，先序遍历的区间 $preS$, $preE$；中序遍历数组 $inorder$，中序遍历的区间 $inS$，$inE$。

终止条件：$preS > preE$ 或者 $inS > inE$ 。

递推工作：

1. 根据 $preorder$ 和 $preS$ ，可以得到根节点的值 $rootV$，通过 $rootV$ 拿到其在 $inorder$ 中的位置 $rootIdx$，所以 $inorder$ 中，左子树的区间为 $[inS, rootIdx-1]$，右子树的区间为 $[rootIdx + 1, inE]$。
2. 将 $preorder$ 划分左右子树部分。左子树的个数应该为 $rootIdx - inS$，所以 $preorder$ 中左子树的区间为 $[preS + 1, preS + rootIdx - inS]$，右子树的区间为 $[preS + rootIdx - inS + 1, preE]$。
3. 创建根节点，根据 $1$、$2$ 步得到的左右子树区间，继续进行递归，将根节点的左右孩子指向递归函数的返回值。

代码：

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if(preorder == null || inorder == null
            || preorder.length == 0 || preorder.length != inorder.length){
        return null;
    }
    return buildTree(
            preorder, 0, preorder.length - 1,
            inorder, 0, inorder.length - 1);
}

private TreeNode buildTree(int[] preOrder, int preStart, int preEnd,
                           int[] inOrder, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) {
        return null;
    }
    int rootVal = preOrder[preStart];
    int rootIdxInOrder = findIndex(inOrder, inStart, inEnd, rootVal);
    TreeNode root = new TreeNode(rootVal);
    // 如何确定 preEnd 的大小?
    // 通过 rootIdxInOrder 其实可以确定 preOrder 中，那部分是属于左子树的
    // 左子树的节点个数为 rootIdxInOrder - inStart，preEnd 应该 preStart + rootIdxInOrder - inStart
    int newPreEnd = preStart + rootIdxInOrder - inStart;
    root.left = buildTree(preOrder, preStart + 1, newPreEnd, inOrder, inStart, rootIdxInOrder - 1);
    root.right = buildTree(preOrder, newPreEnd+1, preEnd, inOrder, rootIdxInOrder + 1, inEnd);
    return root;
}

/**
 * 拿到根节点在中序遍历数组中的索引位置
 */
private int findIndex(int[] inOrder, int s, int e, int root) {
    for (int i = s; i <= e; i++) {
        if (inOrder[i] == root) {
            return i;
        }
    }
    return -1;
}

复杂度分析

• 时间复杂度 $O(N)$：递归共建立 $N$ 个节点，每层递归中的节点建立占用 $O(1)$，寻找根节点位置的循环总共占用$O(N)$，因此使用 $O(N)$ 时间。

• 空间复杂度 $O(N)$ ：最差情况下，树是一个链表，需要占用函数栈的空间为 $O(N)$。当树为满二叉树时，递归深度为 $logN$，占用 $O(logN)$ 的空间。