07 重建二叉树

Lin2J
2021-07-21 / 0 评论 / 79 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

剑指 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)$ 的空间。