面试二叉树看这11个就够了
不知道你有没有这种困惑，虽然刷了很多算法题，当我去面试的时候，面试官让你手写一个算法，可能你对此算法很熟悉，知道实现思路，但是总是不知道该在什么地方写，而且很多边界条件想不全面，一紧张，代码写的乱七八糟。如果遇到没有做过的算法题，思路也不知道从何寻找，那么这篇文章就主要为你解决这几个问题。
《剑指 offer》是准备数据结构与算法面试的一本好书，里边很多面试手写算法很多的注意的问题，但是基本都是用 c++ 实现的，书中每章节的分类都是按照性能和消耗以及手写代码的注意的几大点进行了分类，针对每个不同的点，进行数据结构与算法的混合实现。
二遍刷题，发现了还可以根据自身情况进行整理和分类。全部代码是用 js 书写，都经过 leetcode 标准测试（小部分leetcode 没有的题目），对所有的算法题的特点进行总结分类，手写算法中，如何考虑到全部的边界条件；如果快速多种思路解决，如何将思路快速的转化为代码，这是这一篇重点分享的地方。
二叉树题目共有 11 题，我把这 11 题书中对实现方法和思路有详细的讲解，但是对于个人来说，以后遇到陌生的二叉树的题目怎么进行解决，通过对 11 个题的分析、整理，得出以下几个步骤，首先先来看这 11 个二叉树经典算法题。
ps：如果你已经做过这几道题，而且能够顺利的手写出来，不妨滑到最底部，希望最后的二叉树思路、测试用例以及代码编写的总结对你在面试中有所帮助（这篇文章精华所在）。
no.1
面试题7：重建二叉树
已知前序遍历为{1,2,4,7,3,5,6,8}，中序遍历为{4,7,2,1,5,3,8,6}，它的二叉树是怎么样的？
1、
思路
根据前、中序遍历的特点，（根左右、左根右），先根据前序遍历确定根节点，然后在中序遍历知道该根节点的左右树的数量，反推出前序遍历中左子树的结点有哪些。根据该思路进行递归即可完成二叉树的重建。
2、
测试用例
完全二叉树、非完全二叉树 —— 普通测试。
只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。
空树、前序和中序不匹配 —— 输入测试。
3、
代码实现
1//定义结点 2//classtreenode{ 3//constructor(data){ 4//this.data=data; 5//this.left=null; 6//this.right=null; 7//} 8//} 9 10//参数：前序遍历数组~中序遍历数组 11constreconstructbinarytree=(pre,vin)=>{ 12//判断前序数组和中序数组是否为空 13if(!pre||pre.length===0||!vin||vin.length===0){ 14return; 15} 16//新建二叉树的根节点 17vartreenode={ 18val:pre[0] 19} 20//查找中序遍历中的根节点 21for(vari=0;i{ 2//判断该结点是否为null 3if(pnode==null){ 4return; 5} 6 7//当前结点有右子树且左子树 8if(pnode.right!==null){ 9pnode=pnode.right; 10//判断右子树是否有左子树 11while(pnode.left!==null){ 12pnode=pnode.left; 13} 14returnpnode; 15}else{ 16//判断当前结点是否存在父节点(如果为空,没有下一结点) 17while(pnode.next!==null){ 18if(pnode==pnode.next.left){ 19returnpnode.next; 20}else{ 21pnode=pnode.next; 22} 23} 24//没有下一结点 25returnnull; 26} 27}
no.3
面试题26：树的子结构
输入两棵二叉树 a 和 b，判断 b 是不是 a 的子结构。
1、
思路
通过判断两棵树的根节点否相同，如果相同，则递归判断树剩余的结点是否相同。如果不相同，则递归树的左右子节点进行对比找到相同的根节点。
2、
测试用例
是子结构、不是子结构 —— 普通测试。
只有左子节点、只有右子节点、只有一个结点 —— 特殊测试。
空树 —— 输入测试。
3、
代码实现
1consttreeconstrutor=(nodea,nodeb)=>{ 2constresult=false; 3//判断输入是否为null 4//nodea为null不会有子结构 5if(nodea==null){ 6returnfalse; 7} 8//如果nodeb为null,代表所有子结构比较完成 9if(nodeb==null){ 10returntrue; 11} 12 13//如果根节点相同，则进行子结构全部的验证,返回验证的结果 14if(nodea.data===nodeb.data){ 15result=match(nodea,nodeb) 16} 17 18//如果根节点不相同，继续递归遍历查找相同的根节点 19returntreeconstrutor(nodea.left,nodeb)||treeconstrutor(nodea.right,nodeb) 20} 21 22//匹配根节点相同的子结构 23constmatch=(nodea,nodeb)=>{ 24if(nodea==null){ 25returnfalse; 26} 27if(nodeb==null){ 28returntrue; 29} 30//判断匹配的当前结点是否相同 31if(nodea.data==nodeb.data){ 32//递归匹配其他子节点 33returnmatch(nodea.left,nodeb.left)&&match(nodea.right,nodeb.right); 34} 35 36//如果不相同 37returnfalse; 38}
no.4
面试题27：二叉树的镜像
请完成一个函数，如果一个二叉树，该函数输出它的镜像。
1、
思路
根节点的左右子节点相互交换，继续递归遍历，将子节点的左右结点进行交换，知道遇到叶子节点。
2、
测试用例
完全二叉树、非完全二叉树 —— 普通测试。
只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。
空树 —— 输入测试。
3、
代码实现
1constinsert=(root)=>{ 2//判断根节点是否为null 3if(root==null){ 4return; 5} 6 7//进行结点交换 8lettempnode=root.left; 9root.left=root.right; 10root.right=tempnode; 11 12//递归遍历剩余的子节点 13insert(root.left); 14insert(root.right); 15 16//返回根节点 17returnroot; 18}
no.5
面试题28：对称二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
1、
思路
首先，观察一个对称的二叉树有什么特点？
结构上：在结构上实对称的，某一节点的左子节点和某一节点的右子节点对称。
规律上：我们如果进行前序遍历（根、左、右），然后对前序遍历进行改进（根、右、左），如果是对称的二叉树，他们的遍历结果是相同的。
考虑其他情况：
结点数量不对称
结点值不对称
2、
测试用例
对称二叉树、不对称二叉树（结点数量不对称、结点结构不对称）—— 普通测试。
所有结点值都相同的二叉树 —— 特殊测试。
空二叉树 —— 输入测试。
3、
代码实现
1varissymmetric=(root)=>{ 2//判断二叉树是否为null——输入测试，if(root==null){ 3returntrue; 4} 5 6//判断输入的二叉树,从根节点开始判断是否是对称二叉树 7varsymmetric=(lnode,rnode)=>{ 8//判断左右结点是否都为null 9if(lnode==null&&rnode==null){ 10returntrue; 11} 12//判断其中一个为null另一个不是null 13if(lnode==null&&rnode!==null){ 14returnfalse; 15} 16if(lnode!==null&&rnode==null){ 17returnfalse; 18} 19//判断两个结点的值是否相同 20if(lnode.val!==rnode.val){ 21returnfalse; 22} 23//如果相同，继续递归判断其他的结点 24returnsymmetric(lnode.left,rnode.right)&&symmetric(lnode.right,rnode.left) 25} 26 27symmetric(root.left,root.right) 28}
no.6
面试题32：从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。（按层遍历二叉树）
1、
思路
从根节点开始按层遍历打印结点（自左往右），下一层的遍历是上一层的字节点，但是我们发现想要获取到上层结点的子节点时，上层的父节点已经遍历过去可，想要在获取到，必须存储父节点。然后下层遍历的时候，自左往右取出父节点，依次打印子节点。
上方的解题思路中父节点的存储和遍历让我们想到一个熟悉的数据结构，对了，“先进先出”的思想，那就是队列。在遍历上一层结点的时候，先打印结点值，然后判断是够存在左右子树，如果存在，将给结点入队，直到该层的结点全部遍历完成。然后队列出队，分别打印结点，循环此步骤。
2、
测试用例
完全二叉树、非完全二叉树 —— 普通测试
只有左、右子节点的二叉树、只有一个节点的二叉树 —— 特殊测试
空树 —— 输入测试
3、
代码实现
1、参数：树的根节点。
2、判断是否为空。
3、打印结点值,判断该结点是否存在子节点，如果存在就入队。
4、出队，打印结点
5、循环上述步骤
1varlevelorder=function(root){ 2letresult=[];//存放遍历的结果 3//判断根节点是否为null 4if(root==null){ 5return[]; 6} 7//声明一个队列 8letqueue=[]; 9queue.push(root) 10 11//出队，打印结结点、判断是否存在子节点 12while(queue.length!==0){ 13lettemp=[];//存储每层的结点 14letlen=queue.length; 15for(letj=0;j{ 2//判断数组是否为null 3if(arr.length==0){ 4returntrue; 5} 6 7//取数组最后一个数字为根节点 8letrootval=arr[arr.length-1]; 9 10//搜索小于根节点的值,并记录该结点的下标(除根节点外) 11leti=0; 12for(;irootval){ 14break 15} 16} 17 18//搜索大于根节点的值（除根节点外） 19letj=0; 20for(;jarr[j]){ 22returnfalse; 23} 24} 25 26//递归判断左子节点的值（先判断左子节点是够有值），默认返回true 27letleft=true 28if(i>0){ 29left=ispostorder(arr.slice(0,i)) 30} 31//如果右子树不为空，判断右子树为二叉搜索树 32letright=true 33if(i{ 2//判断输入的二叉树和整数 3if(root==null||targetsum{ 20//将当前跟根节点进行累加 21currentsum=currentsum+root.val; 22 23//存储栈中 24pathstack.push(root.val); 25 26//判断目标值是否相等且是否为叶子节点 27if(currentsum==targetsum&&root.left==null&&root.right==null){ 28//打印路径 29result.push(pathstack.slice(0)) 30} 31 32//如果左子节点不为空 33if(root.left!==null){ 34findpath(root.left,targetsum,currentsum,pathstack,result); 35} 36 37//如果当前结点还有右子树，继续遍历 38if(root.right!==null){ 39findpath(root.right,targetsum,currentsum,pathstack,result); 40} 41 42//该路径遍历到叶子节点，还没有满足条件，则退回到父节点，进行下一结点的累加判断 43pathstack.pop(); 44}
no.9
面试题37：序列化二叉树
请实现两个函数，分别用来序列化二叉树和反序列化二叉树。
1、
思路
1、序列化：遍历二叉树，遇到叶子节点，将其转化为 $ 表示。
2、反序列化：根据前序遍历的特点（根、左、右），进行二叉树的还原。
2、
测试用例
完全二叉树、非完全二叉树 —— 普通测试。
只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。
空树 —— 输入测试。
3、
代码实现
1letresult=[]; 2varserialize=function(root){ 3//判空 4if(root==null){ 5result.push('$'); 6return; 7} 8//前序遍历 9result.push(root.val) 10serialize(root.left) 11serialize(root.right) 12//打印 13console.log(result) 14}; 15 16serialize(symmetricaltree);
no.10
面试题54：二叉树的第 k 大节点
给定一棵二叉搜索树，请找出其中的第 k 大节点。
1、
思路
要想找到第 k 大结点必要要知道排序，二叉树的前、中、后遍历中的中序遍历就是从小到大排序。然后遍历的同时计数找到第 k 大节点。
2、
测试用例
完全二叉树、非完全二叉树 —— 普通测试。
只有左子节点的二叉树、只有右子节点的二叉树、只有一个节点的二叉树 —— 特殊测试。
k 的范围、空树 —— 输入测试。
3、
代码实现
1//求二叉树中第k大节点 2varkthtallest=function(root,k){ 3letres=[] 4//遍历 5constinorder=(root)=>{ 6if(root){ 7inorder(root.left); 8res.push(root.val); 9inorder(root.right); 10} 11} 12//调用 13inorder(root); 14returnres[res.length-k] 15};
no.11
面试题55：二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶子节点依次经过的节点（包含根、叶子节点）形成树的一条路径，最长路径的长度树的深度。
1、
思路
思路一：按层遍历，对按层遍历的算法进行改进，每遍历一次层进行加一。
思路二：寻找最长路径，借助遍历最长路径的设计思路记性改进。只需记录两个子树最深的结点为主。
2、
测试用例
完全二叉树、非完全二叉树 —— 普通测试。
只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。
空树、前序和中序不匹配 —— 输入测试。
3、
代码实现
1varmaxdepth=function(root){ 2//如果根节点为null 3if(root===null)return0; 4 5//递归左子树 6letdepthleft=maxdepth(root.left); 7 8//递归右子树 9letdepthright=maxdepth(root.right); 10 11//将子问题合并求总问题 12returnmath.max(depthleft,depthright)+1; 13};
总结归纳
通过《剑指 offer》以上十一个题，不是做过之后就记住了这么简单，而是通过以上二叉树题型的总结归纳，能不能举一反三，总结出二叉树面试题的解题思路，以后遇到二叉树相面试题能不能通过上边总结出来的步骤进行思考独立解决，这是这篇文章的重点。下面就分别通过解题思路、测试用例以及编写代码进行深入总结。
解题思路总结
1、根据树前（根左右）、中（左根右）、后（左右根）序遍历的规律来解决问题。
通过二叉树的遍历来找到规律，从而找到解题思路。
重建二叉树
根据前、中序遍历，找到二叉树的根节点和左右子树的规律，然后递归构建二叉树。
二叉树的下一节点
根据中序遍历，找出包含任何节点的一下节点的所有可能情况，然后根据情况分别进行判断。
二叉树的后续遍历序列
通过中序遍历找到打印二叉树结点的规律，可以判断此后续遍历是否为二叉树。
二叉树和为某一值的路径
选择二叉树的遍历，对每个节点进行存储判断，然后根据二叉树叶子节点的特点，进行对问题的解决。
二叉树的第 k 大结点
中序遍历的结果是从小到大，然后倒数找到第 k 大数据。
序列化二叉树
遍历二叉树，遇到 null 转化为特殊符号。
2、根据树的结构寻找规律来解决问题
通过二叉树的特点：左子节点小于父节点、右子节点大于父节点、树的节点可以进行递归等，以上特点又是更好的帮我们解决思路。
树的子结构
根据子结构和主体树的特点，对其树的结构进行分析，可以找到解题的思路。
镜像二叉树
观察镜像二叉树的左右子节点交换特点，可以找到解题思路。
对称二叉树
观察对称二叉树有什么特点，在结构上和遍历上寻找特点和规律，可以找到解题思路。
按层遍历二叉树
根据二叉树每层节点的结构关系（父子关系），可以进行每层遍历，通过上层找到下层的遍历结点。
反序列化二叉树
根据遍历的规律和二叉树的规律，将遍历结果生成一棵二叉树。
测试用例总结
通过以上题目中，我将测试用例分为三大种，测试代码的时候，在这三大种进行想就可以了。
※普通测试
※特殊测试
※输入测试
1
普通测试
普通测试从两个方面去想，第一个方面就是问题的本身，比如对称二叉树的判断，普通测试就是分别输入一个对称二叉树和非对称二叉树进行测试。第二个方面就是问题本身没有什么可以找到的测试，比如按层遍历二叉树，它的普通测试就是分别输入完全二叉树（普通二叉树也可以），非完全二叉树进行测试。
2
特殊测试
特殊测试强调的是树的特殊性，特殊的二叉树就那么几个，比如：只有左子节点的二叉树、只有右子节点的二叉树、只有一个节点的二叉树、没有结点的二叉树。
3
输入测试
输入测试，顾名思义，要对用户输入的参数进行判断，比如，你输入一棵树，要判断是否为空。再比如，求最大 k 结点，对 k 的取值范围进行判断。
代码编写
将二叉树的解题思路转化为代码除了熟练最基本的二叉树的增、删、改、查之外，最重要的就是二叉树的递归，因为二叉树的结构决定了用递归解决二叉树问题更加简便。但是递归的书写并不仅简单，因为它有递和归的过程，大脑并不能更好的去处理这些，可以去看之前总结递归的文章《数据结构与算法之递归系列》。
书写二叉树递归问题有一点特别重要，不要尝试的去想那个递归的过程，而是先去寻找到递归的终止条件，然后对每次递归的结果进行判断，然后让他递归去吧，再次强调千万别去思考过程。
学习编程不是做了多少题，而是能不能在做过的题和项目中总结经验，这是快速成长的必要条件。非常感谢各位的大力支持，下一篇我们再见。
大联大品佳力推基于Microchip和Amazon的物联网端到端安全方案
环型变压器的原理
通过四个例子，企业应如何部署人工智能以提供更好的客户体验方式
大咖齐聚、干货满满！2019炬芯Techlife多模态交互技术开发者大会与你共享！
广东省预计到今年底全省将建成5G基站3.48万座
面试二叉树看这11个就够了
复合式盐雾试验机的特点与适用范围
JTAG模式下的MPC5554外部FLASH编程的设计与实现
安富利：智能座舱将重新定义人机交互
聚焦 | 车企自建动力电池工厂,动力电池企业如何应对
从富士康赋能夏普，看中国制造的全球影响力
使用PSIM软件仿真BUCK电路
AM5-DB低压备自投装置 在河北冠益荣信科技公司洞庭变电站工程中的应用
苹果发布会:十三真的香，苹果罕见的减价增配
采用NMOS差分对结构实现低电压运算放大器的设计
华为P10防走丢神器，4种导航系统随意切换
华为Mate 40系列可能会在今年10月正式上市
鸿蒙底层架构是什么
LG G6：高通骁龙835+双摄像头设计，3月10日上市开卖
美高森美批量生产DIGI-G4 OTN处理器
《剑指 offer》是准备数据结构与算法面试的一本好书，里边很多面试手写算法很多的注意的问题，但是基本都是用 c++ 实现的，书中每章节的分类都是按照性能和消耗以及手写代码的注意的几大点进行了分类，针对每个不同的点，进行数据结构与算法的混合实现。
二遍刷题，发现了还可以根据自身情况进行整理和分类。全部代码是用 js 书写，都经过 leetcode 标准测试（小部分leetcode 没有的题目），对所有的算法题的特点进行总结分类，手写算法中，如何考虑到全部的边界条件；如果快速多种思路解决，如何将思路快速的转化为代码，这是这一篇重点分享的地方。
二叉树题目共有 11 题，我把这 11 题书中对实现方法和思路有详细的讲解，但是对于个人来说，以后遇到陌生的二叉树的题目怎么进行解决，通过对 11 个题的分析、整理，得出以下几个步骤，首先先来看这 11 个二叉树经典算法题。
ps：如果你已经做过这几道题，而且能够顺利的手写出来，不妨滑到最底部，希望最后的二叉树思路、测试用例以及代码编写的总结对你在面试中有所帮助（这篇文章精华所在）。
no.1
面试题7：重建二叉树
已知前序遍历为{1,2,4,7,3,5,6,8}，中序遍历为{4,7,2,1,5,3,8,6}，它的二叉树是怎么样的？
1、
思路
根据前、中序遍历的特点，（根左右、左根右），先根据前序遍历确定根节点，然后在中序遍历知道该根节点的左右树的数量，反推出前序遍历中左子树的结点有哪些。根据该思路进行递归即可完成二叉树的重建。
2、
测试用例
完全二叉树、非完全二叉树 —— 普通测试。
只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。
空树、前序和中序不匹配 —— 输入测试。
3、
代码实现
1//定义结点 2//classtreenode{ 3//constructor(data){ 4//this.data=data; 5//this.left=null; 6//this.right=null; 7//} 8//} 9 10//参数：前序遍历数组~中序遍历数组 11constreconstructbinarytree=(pre,vin)=>{ 12//判断前序数组和中序数组是否为空 13if(!pre||pre.length===0||!vin||vin.length===0){ 14return; 15} 16//新建二叉树的根节点 17vartreenode={ 18val:pre[0] 19} 20//查找中序遍历中的根节点 21for(vari=0;i{ 2//判断该结点是否为null 3if(pnode==null){ 4return; 5} 6 7//当前结点有右子树且左子树 8if(pnode.right!==null){ 9pnode=pnode.right; 10//判断右子树是否有左子树 11while(pnode.left!==null){ 12pnode=pnode.left; 13} 14returnpnode; 15}else{ 16//判断当前结点是否存在父节点(如果为空,没有下一结点) 17while(pnode.next!==null){ 18if(pnode==pnode.next.left){ 19returnpnode.next; 20}else{ 21pnode=pnode.next; 22} 23} 24//没有下一结点 25returnnull; 26} 27}
no.3
面试题26：树的子结构
输入两棵二叉树 a 和 b，判断 b 是不是 a 的子结构。
1、
思路
通过判断两棵树的根节点否相同，如果相同，则递归判断树剩余的结点是否相同。如果不相同，则递归树的左右子节点进行对比找到相同的根节点。
2、
测试用例
是子结构、不是子结构 —— 普通测试。
只有左子节点、只有右子节点、只有一个结点 —— 特殊测试。
空树 —— 输入测试。
3、
代码实现
1consttreeconstrutor=(nodea,nodeb)=>{ 2constresult=false; 3//判断输入是否为null 4//nodea为null不会有子结构 5if(nodea==null){ 6returnfalse; 7} 8//如果nodeb为null,代表所有子结构比较完成 9if(nodeb==null){ 10returntrue; 11} 12 13//如果根节点相同，则进行子结构全部的验证,返回验证的结果 14if(nodea.data===nodeb.data){ 15result=match(nodea,nodeb) 16} 17 18//如果根节点不相同，继续递归遍历查找相同的根节点 19returntreeconstrutor(nodea.left,nodeb)||treeconstrutor(nodea.right,nodeb) 20} 21 22//匹配根节点相同的子结构 23constmatch=(nodea,nodeb)=>{ 24if(nodea==null){ 25returnfalse; 26} 27if(nodeb==null){ 28returntrue; 29} 30//判断匹配的当前结点是否相同 31if(nodea.data==nodeb.data){ 32//递归匹配其他子节点 33returnmatch(nodea.left,nodeb.left)&&match(nodea.right,nodeb.right); 34} 35 36//如果不相同 37returnfalse; 38}
no.4
面试题27：二叉树的镜像
请完成一个函数，如果一个二叉树，该函数输出它的镜像。
1、
思路
根节点的左右子节点相互交换，继续递归遍历，将子节点的左右结点进行交换，知道遇到叶子节点。
2、
测试用例
完全二叉树、非完全二叉树 —— 普通测试。
只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。
空树 —— 输入测试。
3、
代码实现
1constinsert=(root)=>{ 2//判断根节点是否为null 3if(root==null){ 4return; 5} 6 7//进行结点交换 8lettempnode=root.left; 9root.left=root.right; 10root.right=tempnode; 11 12//递归遍历剩余的子节点 13insert(root.left); 14insert(root.right); 15 16//返回根节点 17returnroot; 18}
no.5
面试题28：对称二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
1、
思路
首先，观察一个对称的二叉树有什么特点？
结构上：在结构上实对称的，某一节点的左子节点和某一节点的右子节点对称。
规律上：我们如果进行前序遍历（根、左、右），然后对前序遍历进行改进（根、右、左），如果是对称的二叉树，他们的遍历结果是相同的。
考虑其他情况：
结点数量不对称
结点值不对称
2、
测试用例
对称二叉树、不对称二叉树（结点数量不对称、结点结构不对称）—— 普通测试。
所有结点值都相同的二叉树 —— 特殊测试。
空二叉树 —— 输入测试。
3、
代码实现
1varissymmetric=(root)=>{ 2//判断二叉树是否为null——输入测试，if(root==null){ 3returntrue; 4} 5 6//判断输入的二叉树,从根节点开始判断是否是对称二叉树 7varsymmetric=(lnode,rnode)=>{ 8//判断左右结点是否都为null 9if(lnode==null&&rnode==null){ 10returntrue; 11} 12//判断其中一个为null另一个不是null 13if(lnode==null&&rnode!==null){ 14returnfalse; 15} 16if(lnode!==null&&rnode==null){ 17returnfalse; 18} 19//判断两个结点的值是否相同 20if(lnode.val!==rnode.val){ 21returnfalse; 22} 23//如果相同，继续递归判断其他的结点 24returnsymmetric(lnode.left,rnode.right)&&symmetric(lnode.right,rnode.left) 25} 26 27symmetric(root.left,root.right) 28}
no.6
面试题32：从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。（按层遍历二叉树）
1、
思路
从根节点开始按层遍历打印结点（自左往右），下一层的遍历是上一层的字节点，但是我们发现想要获取到上层结点的子节点时，上层的父节点已经遍历过去可，想要在获取到，必须存储父节点。然后下层遍历的时候，自左往右取出父节点，依次打印子节点。
上方的解题思路中父节点的存储和遍历让我们想到一个熟悉的数据结构，对了，“先进先出”的思想，那就是队列。在遍历上一层结点的时候，先打印结点值，然后判断是够存在左右子树，如果存在，将给结点入队，直到该层的结点全部遍历完成。然后队列出队，分别打印结点，循环此步骤。
2、
测试用例
完全二叉树、非完全二叉树 —— 普通测试
只有左、右子节点的二叉树、只有一个节点的二叉树 —— 特殊测试
空树 —— 输入测试
3、
代码实现
1、参数：树的根节点。
2、判断是否为空。
3、打印结点值,判断该结点是否存在子节点，如果存在就入队。
4、出队，打印结点
5、循环上述步骤
1varlevelorder=function(root){ 2letresult=[];//存放遍历的结果 3//判断根节点是否为null 4if(root==null){ 5return[]; 6} 7//声明一个队列 8letqueue=[]; 9queue.push(root) 10 11//出队，打印结结点、判断是否存在子节点 12while(queue.length!==0){ 13lettemp=[];//存储每层的结点 14letlen=queue.length; 15for(letj=0;j{ 2//判断数组是否为null 3if(arr.length==0){ 4returntrue; 5} 6 7//取数组最后一个数字为根节点 8letrootval=arr[arr.length-1]; 9 10//搜索小于根节点的值,并记录该结点的下标(除根节点外) 11leti=0; 12for(;irootval){ 14break 15} 16} 17 18//搜索大于根节点的值（除根节点外） 19letj=0; 20for(;jarr[j]){ 22returnfalse; 23} 24} 25 26//递归判断左子节点的值（先判断左子节点是够有值），默认返回true 27letleft=true 28if(i>0){ 29left=ispostorder(arr.slice(0,i)) 30} 31//如果右子树不为空，判断右子树为二叉搜索树 32letright=true 33if(i{ 2//判断输入的二叉树和整数 3if(root==null||targetsum{ 20//将当前跟根节点进行累加 21currentsum=currentsum+root.val; 22 23//存储栈中 24pathstack.push(root.val); 25 26//判断目标值是否相等且是否为叶子节点 27if(currentsum==targetsum&&root.left==null&&root.right==null){ 28//打印路径 29result.push(pathstack.slice(0)) 30} 31 32//如果左子节点不为空 33if(root.left!==null){ 34findpath(root.left,targetsum,currentsum,pathstack,result); 35} 36 37//如果当前结点还有右子树，继续遍历 38if(root.right!==null){ 39findpath(root.right,targetsum,currentsum,pathstack,result); 40} 41 42//该路径遍历到叶子节点，还没有满足条件，则退回到父节点，进行下一结点的累加判断 43pathstack.pop(); 44}
no.9
面试题37：序列化二叉树
请实现两个函数，分别用来序列化二叉树和反序列化二叉树。
1、
思路
1、序列化：遍历二叉树，遇到叶子节点，将其转化为 $ 表示。
2、反序列化：根据前序遍历的特点（根、左、右），进行二叉树的还原。
2、
测试用例
完全二叉树、非完全二叉树 —— 普通测试。
只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。
空树 —— 输入测试。
3、
代码实现
1letresult=[]; 2varserialize=function(root){ 3//判空 4if(root==null){ 5result.push('$'); 6return; 7} 8//前序遍历 9result.push(root.val) 10serialize(root.left) 11serialize(root.right) 12//打印 13console.log(result) 14}; 15 16serialize(symmetricaltree);
no.10
面试题54：二叉树的第 k 大节点
给定一棵二叉搜索树，请找出其中的第 k 大节点。
1、
思路
要想找到第 k 大结点必要要知道排序，二叉树的前、中、后遍历中的中序遍历就是从小到大排序。然后遍历的同时计数找到第 k 大节点。
2、
测试用例
完全二叉树、非完全二叉树 —— 普通测试。
只有左子节点的二叉树、只有右子节点的二叉树、只有一个节点的二叉树 —— 特殊测试。
k 的范围、空树 —— 输入测试。
3、
代码实现
1//求二叉树中第k大节点 2varkthtallest=function(root,k){ 3letres=[] 4//遍历 5constinorder=(root)=>{ 6if(root){ 7inorder(root.left); 8res.push(root.val); 9inorder(root.right); 10} 11} 12//调用 13inorder(root); 14returnres[res.length-k] 15};
no.11
面试题55：二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶子节点依次经过的节点（包含根、叶子节点）形成树的一条路径，最长路径的长度树的深度。
1、
思路
思路一：按层遍历，对按层遍历的算法进行改进，每遍历一次层进行加一。
思路二：寻找最长路径，借助遍历最长路径的设计思路记性改进。只需记录两个子树最深的结点为主。
2、
测试用例
完全二叉树、非完全二叉树 —— 普通测试。
只有左子节点二叉树，只有右子节点、只有一个结点的二叉树 —— 特殊二叉树测试。
空树、前序和中序不匹配 —— 输入测试。
3、
代码实现
1varmaxdepth=function(root){ 2//如果根节点为null 3if(root===null)return0; 4 5//递归左子树 6letdepthleft=maxdepth(root.left); 7 8//递归右子树 9letdepthright=maxdepth(root.right); 10 11//将子问题合并求总问题 12returnmath.max(depthleft,depthright)+1; 13};
总结归纳
通过《剑指 offer》以上十一个题，不是做过之后就记住了这么简单，而是通过以上二叉树题型的总结归纳，能不能举一反三，总结出二叉树面试题的解题思路，以后遇到二叉树相面试题能不能通过上边总结出来的步骤进行思考独立解决，这是这篇文章的重点。下面就分别通过解题思路、测试用例以及编写代码进行深入总结。
解题思路总结
1、根据树前（根左右）、中（左根右）、后（左右根）序遍历的规律来解决问题。
通过二叉树的遍历来找到规律，从而找到解题思路。
重建二叉树
根据前、中序遍历，找到二叉树的根节点和左右子树的规律，然后递归构建二叉树。
二叉树的下一节点
根据中序遍历，找出包含任何节点的一下节点的所有可能情况，然后根据情况分别进行判断。
二叉树的后续遍历序列
通过中序遍历找到打印二叉树结点的规律，可以判断此后续遍历是否为二叉树。
二叉树和为某一值的路径
选择二叉树的遍历，对每个节点进行存储判断，然后根据二叉树叶子节点的特点，进行对问题的解决。
二叉树的第 k 大结点
中序遍历的结果是从小到大，然后倒数找到第 k 大数据。
序列化二叉树
遍历二叉树，遇到 null 转化为特殊符号。
2、根据树的结构寻找规律来解决问题
通过二叉树的特点：左子节点小于父节点、右子节点大于父节点、树的节点可以进行递归等，以上特点又是更好的帮我们解决思路。
树的子结构
根据子结构和主体树的特点，对其树的结构进行分析，可以找到解题的思路。
镜像二叉树
观察镜像二叉树的左右子节点交换特点，可以找到解题思路。
对称二叉树
观察对称二叉树有什么特点，在结构上和遍历上寻找特点和规律，可以找到解题思路。
按层遍历二叉树
根据二叉树每层节点的结构关系（父子关系），可以进行每层遍历，通过上层找到下层的遍历结点。
反序列化二叉树
根据遍历的规律和二叉树的规律，将遍历结果生成一棵二叉树。
测试用例总结
通过以上题目中，我将测试用例分为三大种，测试代码的时候，在这三大种进行想就可以了。
※普通测试
※特殊测试
※输入测试
1
普通测试
普通测试从两个方面去想，第一个方面就是问题的本身，比如对称二叉树的判断，普通测试就是分别输入一个对称二叉树和非对称二叉树进行测试。第二个方面就是问题本身没有什么可以找到的测试，比如按层遍历二叉树，它的普通测试就是分别输入完全二叉树（普通二叉树也可以），非完全二叉树进行测试。
2
特殊测试
特殊测试强调的是树的特殊性，特殊的二叉树就那么几个，比如：只有左子节点的二叉树、只有右子节点的二叉树、只有一个节点的二叉树、没有结点的二叉树。
3
输入测试
输入测试，顾名思义，要对用户输入的参数进行判断，比如，你输入一棵树，要判断是否为空。再比如，求最大 k 结点，对 k 的取值范围进行判断。
代码编写
将二叉树的解题思路转化为代码除了熟练最基本的二叉树的增、删、改、查之外，最重要的就是二叉树的递归，因为二叉树的结构决定了用递归解决二叉树问题更加简便。但是递归的书写并不仅简单，因为它有递和归的过程，大脑并不能更好的去处理这些，可以去看之前总结递归的文章《数据结构与算法之递归系列》。
书写二叉树递归问题有一点特别重要，不要尝试的去想那个递归的过程，而是先去寻找到递归的终止条件，然后对每次递归的结果进行判断，然后让他递归去吧，再次强调千万别去思考过程。
学习编程不是做了多少题，而是能不能在做过的题和项目中总结经验，这是快速成长的必要条件。非常感谢各位的大力支持，下一篇我们再见。
大联大品佳力推基于Microchip和Amazon的物联网端到端安全方案
环型变压器的原理
通过四个例子，企业应如何部署人工智能以提供更好的客户体验方式
大咖齐聚、干货满满！2019炬芯Techlife多模态交互技术开发者大会与你共享！
广东省预计到今年底全省将建成5G基站3.48万座
面试二叉树看这11个就够了
复合式盐雾试验机的特点与适用范围
JTAG模式下的MPC5554外部FLASH编程的设计与实现
安富利：智能座舱将重新定义人机交互
聚焦 | 车企自建动力电池工厂,动力电池企业如何应对
从富士康赋能夏普，看中国制造的全球影响力
使用PSIM软件仿真BUCK电路
AM5-DB低压备自投装置 在河北冠益荣信科技公司洞庭变电站工程中的应用
苹果发布会:十三真的香，苹果罕见的减价增配
采用NMOS差分对结构实现低电压运算放大器的设计
华为P10防走丢神器，4种导航系统随意切换
华为Mate 40系列可能会在今年10月正式上市
鸿蒙底层架构是什么
LG G6：高通骁龙835+双摄像头设计，3月10日上市开卖
美高森美批量生产DIGI-G4 OTN处理器