剑指 Offer 07. 重建二叉树

大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面试的时候紧张也能做对。

AlgoMooc 算法慕课网,每道题目都有动画和图片,致力于帮助每个程序员通过算法面试!

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列面试题 07. 重建二叉树

题目汇总链接:https://www.algomooc.com/jianzhioffer

一、题目描述

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

限制:

0 <= 节点个数 <= 5000

二、题目解析

首先,我们先来复习一下前序遍历、中序遍历。(在下方的视频中也有讲解)

前序遍历

二叉树的前序遍历顺序是:根节点、左子树、右子树,每个子树的遍历顺序同样满足前序遍历顺序。

中序遍历

二叉树的中序遍历顺序是:左子树、根节点、右子树,每个子树的遍历顺序同样满足中序遍历顺序。

复习过后,我们可以得出以下结论:

  • 在二叉树的 前序遍历 序列中,第一个数字总是树的根结点的值;
  • 在二叉树的 中序遍历 序列中,根结点的值在序列的中间,左子树的结点的值位于根结点的值的左边,而右子树的结点的值位于根结点的值的右边

以本题的序列为例,前序遍历序列的第一个数字 3 就是根结点的值,在中序遍历序列,找到根结点值的位置。根据中序遍历特点,在根结点的值 3 前面的数字都是左子树结点的值,在根结点的值 3 后面的数字都是右子树结点的值。

二叉树很重要的一个性质是递归,在找到了左子树、右子树的前序遍历序列和中序遍历序列后,我们可以按照同样的方法去确定 子左子树子右子树 的构建。

具体的代码编写思路如下(来源于 Krahets's Blog):

  • 递推参数: 前序遍历中根节点的索引pre_root_idx、中序遍历左边界in_left_idx、中序遍历右边界in_right_idx
  • 终止条件:in_left_idx > in_right_idx ,子树中序遍历为空,说明已经越过叶子节点,此时返回 null 。
  • 递推工作:
    1. 建立根节点 root : 值为前序遍历中索引为pre_root_idx的节点值。
    2. 搜索根节点 root 在中序遍历的索引 i : 为了提升搜索效率,本题解使用哈希表 map 预存储中序遍历的值与索引的映射关系,每次搜索的时间复杂度为 O(1)。
    3. 构建根节点 root 的左子树和右子树:通过调用 recursive() 方法开启下一层递归。
      • 左子树: 根节点索引为 pre_root_idx + 1 ,中序遍历的左右边界分别为 in_left_idxi - 1
      • 右子树: 根节点索引为 i - in_left_idx + pre_root_idx + 1(即:根节点索引 + 左子树长度 + 1),中序遍历的左右边界分别为 i + 1in_right_idx
  • 返回值: 返回 root,含义是当前递归层级建立的根节点 root 为上一递归层级的根节点的左或右子节点。

三、动画描述

隐藏内容

此处内容需要权限查看

  • 普通用户特权:5积分
  • 会员用户特权:免费
  • 算法训练营永久会员用户特权:免费推荐
会员免费查看

四、图片描述

面试题07. 重建二叉树.002

面试题07. 重建二叉树.003

面试题07. 重建二叉树.004

面试题07. 重建二叉树.005

面试题07. 重建二叉树.006

面试题07. 重建二叉树.007

面试题07. 重建二叉树.008

面试题07. 重建二叉树.009

面试题07. 重建二叉树.010

面试题07. 重建二叉树.011

面试题07. 重建二叉树.012

面试题07. 重建二叉树.013

面试题07. 重建二叉树.014

面试题07. 重建二叉树.015

面试题07. 重建二叉树.016

面试题07. 重建二叉树.017

面试题07. 重建二叉树.018

面试题07. 重建二叉树.019

面试题07. 重建二叉树.020

面试题07. 重建二叉树.021

面试题07. 重建二叉树.022

面试题07. 重建二叉树.023

面试题07. 重建二叉树.024

面试题07. 重建二叉树.025

面试题07. 重建二叉树.026

面试题07. 重建二叉树.027

面试题07. 重建二叉树.028

面试题07. 重建二叉树.029

面试题07. 重建二叉树.030

面试题07. 重建二叉树.031

面试题07. 重建二叉树.032

面试题07. 重建二叉树.033

面试题07. 重建二叉树.034

面试题07. 重建二叉树.035

面试题07. 重建二叉树.036

面试题07. 重建二叉树.037

面试题07. 重建二叉树.038

面试题07. 重建二叉树.039

面试题07. 重建二叉树.040

面试题07. 重建二叉树.041

面试题07. 重建二叉树.042

面试题07. 重建二叉树.043

面试题07. 重建二叉树.044

面试题07. 重建二叉树.045

面试题07. 重建二叉树.046

面试题07. 重建二叉树.047

面试题07. 重建二叉树.048

面试题07. 重建二叉树.049

面试题07. 重建二叉树.050

面试题07. 重建二叉树.051

面试题07. 重建二叉树.052

面试题07. 重建二叉树.053

面试题07. 重建二叉树.054

面试题07. 重建二叉树.055

面试题07. 重建二叉树.056

面试题07. 重建二叉树.057

面试题07. 重建二叉树.058

面试题07. 重建二叉树.059

面试题07. 重建二叉树.060

面试题07. 重建二叉树.061

面试题07. 重建二叉树.062

面试题07. 重建二叉树.063

面试题07. 重建二叉树.064

面试题07. 重建二叉树.065

面试题07. 重建二叉树.066

面试题07. 重建二叉树.067

面试题07. 重建二叉树.068

面试题07. 重建二叉树.069

面试题07. 重建二叉树.070

面试题07. 重建二叉树.071

面试题07. 重建二叉树.072

面试题07. 重建二叉树.073

面试题07. 重建二叉树.074

面试题07. 重建二叉树.075

面试题07. 重建二叉树.076

面试题07. 重建二叉树.077

面试题07. 重建二叉树.078

面试题07. 重建二叉树.079

五、参考代码

class Solution {
    //在中序序列中查找与前序序列首结点相同元素的时候,如果使用 while 循环去一个个找效率很慢
    //这里我们借助数据结构 HashMap 来辅助查找,在开始递归之前把所有的中序序列的元素和它们所在的下标存到一个 map 中,这样查找的时间复杂度是 O(logn)
    HashMap map = new HashMap<>();

    //保留的前序遍历
    int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        //在开始递归之前把所有的中序序列的元素和它们所在的下标存到一个 map 中
        for (int i = 0; i < preorder.length; i++) {
            map.put(inorder[i], i);
        }
        //二叉树的重要性质是递归
        return recursive(0,0,inorder.length-1);
    }

    /** 根据前序遍历序列和中序遍历序列重新组建二叉树
     * @param pre_root_idx 前序遍历的索引
     * @param in_left_idx  中序遍历左边界的索引
     * @param in_right_idx 中序遍历右边界的索引
     */
    public TreeNode recursive(int pre_root_idx, int in_left_idx, int in_right_idx) {

        //子树中序遍历为空,说明已经越过叶子节点,此时返回 nul
        if (in_left_idx > in_right_idx) {
            return null;
        }

        //root_idx是在前序里面的
        TreeNode root = new TreeNode(preorder[pre_root_idx]);

        // 通过 map ,根据前序的根节点的值,在中序中获取当前根的索引
        int idx = map.get(preorder[pre_root_idx]);

        //左子树的根节点就是 左子树的(前序遍历)第一个,就是 +1 ,左边边界就是 left ,右边边界是中间区分的idx-1
        root.left = recursive(pre_root_idx + 1, in_left_idx, idx - 1);

        //右子树的根,就是右子树(前序遍历)的第一个,就是当前根节点 加上左子树的数量
        root.right = recursive(pre_root_idx + (idx-1 - in_left_idx +1)  + 1, idx + 1, in_right_idx);

        return root;
    }
}

这段代码的一个难点就是 root.leftroot.right ,我这里抽离出来详细解释一下。

1、root.left

2、root.right

六、复杂度分析

时间复杂度

时间复杂度为 O(N)。

空间复杂度

空间复杂度为 O(N)。

七、相关标签

  • 递归
  • 哈希表

八、参考来源