别再翻了，面试二叉树看这 11 个就够了~

àì夳堔傛蜴生んèń 2023-06-08 10:54 7阅读 0赞

## 写在前边 ##

**数据结构与算法：**

不知道你有没有这种困惑，虽然刷了很多算法题，当我去面试的时候，面试官让你手写一个算法，可能你对此算法很熟悉，知道实现思路，但是总是不知道该在什么地方写，而且很多边界条件想不全面，一紧张，代码写的乱七八糟。如果遇到没有做过的算法题，思路也不知道从何寻找。面试吃了亏之后，我就慢慢的做出总结，开始分类的把数据结构所有的题型和解题思路每周刷题做出的系统性总结写在了 Github。欢迎关注和 star： 「[数据结构与算法仓库][Link 1]」

PS:如果你刚刚在学习数据结构和算法，请务必把最简单的题弄懂，所有的入门的数据结构与算法从简单到复杂进行了全面的梳理。  
「[初学者必会的 30 道数据结构与算法][30]」

如果你对数据结构和算法有了一定的了解和认识，上边的入门算法题已经可以轻松实现，那么可以尝试着解决 LeetCode 上总结的 30 道题，我把解题思路、测试用例、代码实现做了详细的整理，建议先自己尝试的解决哦，收藏 + 关注，欢迎 Star。「[必会的 30 道 LeetCode 经典算法题][30 _ LeetCode]」

**网络协议原理：**

除了算法之外，面试最注重的就是网络原理，因为我本身上的学校很烂，课上只是讲点皮毛，当时也没重视这一块，所以在大三面试的时候吃了大亏，然后开始重视了起来，这部分虽然理论上偏多，但是从最基础的开始学习需要有个引导，上来就是 TCP 和 HTTP，想必学起来很吃力吧。然后我尝试着去根源上学习网络原理，为什么会有这些，所以边学习，边整理成了文章分享给学习网络原理这一块的内容，每周 Github 都会更新~ 「[猛戳这里查看仓库][Link 1]」

— 一下是正文 ----

《剑指 offer》是准备数据结构与算法面试的一本好书，里边很多面试手写算法很多的注意的问题，但是基本都是用 C++ 实现的，书中每章节的分类都是按照性能和消耗以及手写代码的注意的几大点进行了分类，针对每个不同的点，进行数据结构与算法的混合实现。

二遍刷题，发现了还可以根据自身情况进行整理和分类。全部代码是用 JS 书写，都经过 Leetcode 标准测试（小部分Leetcode 没有的题目），对所有的算法题的特点进行总结分类，手写算法中，如何考虑到全部的边界条件；如果快速多种思路解决，如何将思路快速的转化为代码，这是这一篇重点分享的地方。

二叉树题目共有 11 题，我把这 11 题书中对实现方法和思路有详细的讲解，但是对于个人来说，以后遇到陌生的二叉树的题目怎么进行解决，通过对 11 个题的分析、整理，得出以下几个步骤，首先先来看这 11 个二叉树经典算法题。

> PS：如果你已经做过这几道题，而且能够顺利的手写出来，不妨滑到最底部，希望最后的二叉树思路、测试用例以及代码编写的总结对你在面试中有所帮助（这篇文章精华所在）。

## 11 道精华二叉树面试题 ##

### 1.1 面试题7：重建二叉树 ###

> 已知前序遍历为\{1,2,4,7,3,5,6,8\}，中序遍历为\{4,7,2,1,5,3,8,6\}，它的二叉树是怎么样的？

**1、思路**

根据前、中序遍历的特点，（根左右、左根右），先根据前序遍历确定根节点，然后在中序遍历知道该根节点的左右树的数量，反推出前序遍历中左子树的结点有哪些。根据该思路进行递归即可完成二叉树的重建。

**2、 测试用例**

*  完全二叉树、非完全二叉树 —— 普通测试。
 *  只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。
 *  空树、前序和中序不匹配 —— 输入测试。

**3、代码实现**

1 // 定义结点
     2 // class TreeNode{
     3 //     constructor(data){
     4 //         this.data = data;
     5 //         this.left = null;
     6 //         this.right = null;
     7 //     } 
     8 // }
     9
    10 // 参数：前序遍历数组 ~ 中序遍历数组
    11 const reConstructBinaryTree = (pre, vin)=>{
    12    // 判断前序数组和中序数组是否为空
    13    if(!pre || pre.length === 0 || !vin || vin.length === 0){
    14        return;
    15    }
    16    // 新建二叉树的根节点
    17    var treeNode = {
    18        val: pre[0]
    19    }
    20    // 查找中序遍历中的根节点
    21    for(var i = 0; i < pre.length; i++) {
    22        if (vin[i] === pre[0]) {
    23            // 将左子树的前中序遍历分割开
    24            treeNode.left = reConstructBinaryTree(pre.slice(1, i+1), vin.slice(0, i));
    25            // 将右子树的前中序遍历分割开
    26            treeNode.right = reConstructBinaryTree(pre.slice(i+1),vin.slice(i+1));
    27        }
    28    }
    29    // 返回该根节点
    30    return treeNode;
    31 }
    32
    33 let pre = [1,2,4,7,3,5,6,8]; // 前序遍历
    34 let vin = [4,7,2,1,5,3,8,6]; // 中序遍历 
    35 console.log(reConstructBinaryTree(pre,vin));

### 1.2 二叉树的下一节点 ###

> 给定一个二叉树的节点，如何找出中序遍历的下一节点。有两个指向左右子树的指针，还有一个指向父节点的指针。

面试题8：\[[题目解析][Link 2]\]

### 1.3 树的子结构 ###

> 输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。

面试题26：\[[题目解析][Link 3]\]

### 1.4 二叉树的镜像 ###

> 请完成一个函数，如果一个二叉树，该函数输出它的镜像。

面试题27：\[[题目解析][Link 4]\]

### 1.5 对称二叉树 ###

> 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

面试题28：\[[题目解析][Link 5]\]

### 1.6 从上到下打印二叉树 ###

> 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。（按层遍历二叉树）

面试题32：\[[题目解析][Link 6]\]

### 1.7 二叉树的后序遍历序列 ###

> 输入一个整数数组，判断该数组是不是某二叉搜索树的后续遍历。如果是返回 true，如果不是返回 false。假设输入的任意两个数字互不相同。

面试题33：\[[题目解析][Link 7]\]

### 1.8 二叉树和为某一值路径 ###

> 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输出整数的所有路径。从树的根节点开始往下一直到叶子节点所经过的节点形成一条路径。

面试34：\[[题目解析][Link 8]\]

### 1.9 序列化二叉树 ###

> 请实现两个函数，分别用来序列化二叉树和反序列化二叉树。

面试题37：\[[题目解析][Link 9]\]

### 1.10 二叉树的第 K 大节点 ###

> 给定一棵二叉搜索树，请找出其中的第 K 大节点。

面试题54：\[[题目解析][Link 10]\]

### 1.11 二叉树的深度 ###

> 输入一棵二叉树的根节点，求该树的深度。从根节点到叶子节点依次经过的节点（包含根、叶子节点）形成树的一条路径，最长路径的长度树的深度。

面试题55:\[[题目解析][Link 11]\]

## 总结归纳 ##

通过《剑指 offer》以上十一个题，不是做过之后就记住了这么简单，而是通过以上二叉树题型的总结归纳，能不能举一反三，总结出二叉树面试题的解题思路，以后遇到二叉树相面试题能不能通过上边总结出来的步骤进行思考独立解决，这是这篇文章的重点。下面就分别通过解题思路、测试用例以及编写代码进行深入总结。

### 一、解题思路总结 ###

1、根据树前（根左右）、中（左根右）、后（左右根）序遍历的规律来解决问题。

> 通过二叉树的遍历来找到规律，从而找到解题思路。

*  重建二叉树
    
    根据前、中序遍历，找到二叉树的根节点和左右子树的规律，然后递归构建二叉树。
 *  二叉树的下一节点
    
    根据中序遍历，找出包含任何节点的一下节点的所有可能情况，然后根据情况分别进行判断。
 *  二叉树的后续遍历序列
    
    通过中序遍历找到打印二叉树结点的规律，可以判断此后续遍历是否为二叉树。
 *  二叉树和为某一值的路径
    
    选择二叉树的遍历，对每个节点进行存储判断，然后根据二叉树叶子节点的特点，进行对问题的解决。
 *  二叉树的第 K 大结点
    
    中序遍历的结果是从小到大，然后倒数找到第 K 大数据。
 *  序列化二叉树
    
    遍历二叉树，遇到 null 转化为特殊符号。

2、根据树的结构寻找规律来解决问题

> 通过二叉树的特点：左子节点小于父节点、右子节点大于父节点、树的节点可以进行递归等，以上特点又是更好的帮我们解决思路。

*  树的子结构
    
    根据子结构和主体树的特点，对其树的结构进行分析，可以找到解题的思路。
 *  镜像二叉树
    
    观察镜像二叉树的左右子节点交换特点，可以找到解题思路。
 *  对称二叉树
    
    观察对称二叉树有什么特点，在结构上和遍历上寻找特点和规律，可以找到解题思路。
 *  按层遍历二叉树
    
    根据二叉树每层节点的结构关系（父子关系），可以进行每层遍历，通过上层找到下层的遍历结点。
 *  反序列化二叉树
    
    根据遍历的规律和二叉树的规律，将遍历结果生成一棵二叉树。

### 二、测试用例 ###

通过以上题目中，我将测试用例分为三大种，测试代码的时候，在这三大种进行想就可以了。

*  **普通测试**
 *  **特殊测试**
 *  **输入测试**

1、普通测试

普通测试从两个方面去想，第一个方面就是问题的本身，比如对称二叉树的判断，普通测试就是分别输入一个对称二叉树和非对称二叉树进行测试。第二个方面就是问题本身没有什么可以找到的测试，比如按层遍历二叉树，它的普通测试就是分别输入完全二叉树（普通二叉树也可以），非完全二叉树进行测试。

2、特殊测试

特殊测试强调的是树的特殊性，特殊的二叉树就那么几个，比如：只有左子节点的二叉树、只有右子节点的二叉树、只有一个节点的二叉树、没有结点的二叉树。

3、输入测试

输入测试，顾名思义，要对用户输入的参数进行判断，比如，你输入一棵树，要判断是否为空。再比如，求最大 K 结点，对 K 的取值范围进行判断。

### 三、代码编写 ###

将二叉树的解题思路转化为代码除了熟练最基本的二叉树的增、删、改、查之外，最重要的就是二叉树的递归，因为二叉树的结构决定了用递归解决二叉树问题更加简便。但是递归的书写并不仅简单，因为它有递和归的过程，大脑并不能更好的去处理这些，可以去看之前总结递归的文章《[数据结构与算法之递归系列][Link 12]》。

书写二叉树递归问题有一点特别重要，不要尝试的去想那个递归的过程，而是先去寻找到递归的终止条件，然后对每次递归的结果进行判断，然后让他递归去吧，再次强调千万别去思考过程。

## 后记 ##

刷了一遍剑指 offer 没有领略到这些题的精华所在，然后开始刷第二遍、第三遍、第四遍… 逐渐的对同一类型的题做出总结，第一周完成了所有二叉树面试题的总结，下一周会选择下一类型面试题进行攻克，打算用两个月的时间，将剑指 offer 所有的面试题型进行体系化的总结、归纳，边学习、边分享。「[猛戳剑指 offer 仓库，和我一起打卡][offer]」

[Link 1]: https://github.com/luxiangqiang/Blog
[30]: https://github.com/luxiangqiang/Data-Structure-Coding
[30 _ LeetCode]: https://github.com/luxiangqiang/JS-LeetCode
[Link 2]: https://github.com/luxiangqiang/JianZhi-Offer_JavaScript/blob/master/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E4%B8%8B%E4%B8%80%E8%8A%82%E7%82%B9.md
[Link 3]: https://github.com/luxiangqiang/JianZhi-Offer_JavaScript/blob/master/%E6%A0%91%E7%9A%84%E5%AD%90%E7%BB%93%E6%9E%84.md
[Link 4]: https://github.com/luxiangqiang/JianZhi-Offer_JavaScript/blob/master/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%95%9C%E5%83%8F.md
[Link 5]: https://github.com/luxiangqiang/JianZhi-Offer_JavaScript/blob/master/%E5%AF%B9%E7%A7%B0%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91.md
[Link 6]: https://github.com/luxiangqiang/JianZhi-Offer_JavaScript/blob/master/%E4%BB%8E%E4%B8%8A%E6%89%93%E5%8D%B0%E4%BA%8C%E5%8F%89%E6%A0%91.md
[Link 7]: https://github.com/luxiangqiang/JianZhi-Offer_JavaScript/blob/master/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E5%90%8E%E7%BB%AD%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97.md
[Link 8]: https://github.com/luxiangqiang/JianZhi-Offer_JavaScript/blob/master/%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E5%92%8C%E4%B8%BA%E6%9F%90%E4%B8%80%E5%80%BC%E7%9A%84%E8%B7%AF%E5%BE%84.md
[Link 9]: https://github.com/luxiangqiang/JianZhi-Offer_JavaScript/blob/master/%E5%BA%8F%E5%88%97%E5%8C%96%E4%BA%8C%E5%8F%89%E6%A0%91%E5%92%8C%E5%8F%8D%E5%BA%8F%E5%88%97%E5%8C%96%E4%BA%8C%E5%8F%89%E6%A0%91.md
[Link 10]: https://github.com/luxiangqiang/JianZhi-Offer_JavaScript/blob/master/%E4%BA%8C%E5%8F%89%E6%A0%91%E6%90%9C%E7%B4%A2%E7%AC%AC%20K%20%E5%A4%A7%E7%BB%93%E7%82%B9.md
[Link 11]: https://github.com/luxiangqiang/JianZhi-Offer_JavaScript/blob/master/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%B7%B1%E5%BA%A6.md
[Link 12]: https://github.com/luxiangqiang/Blog/blob/master/articel/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E7%B3%BB%E5%88%97/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E4%B9%8B%E9%80%92%E5%BD%92%E7%B3%BB%E5%88%97.md
[offer]: https://github.com/luxiangqiang/JianZhi-Offer_JavaScript