二叉树是一种数据结构，分支类型复杂。本文为介绍性文章，仅介绍一些基本的二叉树题型。二叉搜索树等本文不做介绍。二叉树其实是链表的升级版，即链表同时有两个Next指针，就变成了二叉树。二叉树可以根据一些特性降低查找到logn的时间复杂度，比如查找二叉树，堆的数据结构也是一种特殊的二叉树，可以随时间寻找最大值或最小值O(1)的复杂性。因此，二叉树的变种很多，都可以很好的解决特定场景的问题。精读入门二叉树，必须了解二叉树的三种遍历策略，即：前序遍历、中序遍历、后序遍历，都属于深度优先遍历。所谓前中后是指什么时候访问节点值，其余时机先左后右访问子节点。比如前序遍历是先访问值，再访问左右；后续遍历是先访问左右，再访问值；中序遍历是left、value、right。递归遍历树非常简单：functionvisitTree(node:TreeNode){//三选一：前序遍历//console.log(node.val)visitTree(node.left)//三选一三：中序遍历//console.log(node.val)visitTree(node.right)//三选一：后序遍历//console.log(node.val)}当然，我们需要利用二叉树的三个遍历特性来解决问题，比如重建一棵二叉树。重建一棵二叉树重建一棵二叉树是一道中级问题，题目如下：输入某棵二叉树的前序遍历和中序遍历的结果，请重建二叉树。假设输入的前序遍历和中序遍历的结果都不包含重复数。比如先序遍历preorder=[3,9,20,15,7]inorder遍历inorder=[9,3,15,20,7]会先给你二叉树的前序和中序遍历的结果，让你重建二叉树，这种逆向思维问题就难多了。仔细观察遍历特征，我们或许可以推断出一些关键节点的位置，然后通过递归切分数组来解决问题。前序遍历中第一个访问的一定是根节点，所以3一定是根节点，然后我们在中序遍历中找到3，所以左边是所有左子树的中序遍历结果，右边是所有右子树的中间中序遍历结果，我们只需要找到左子树的前序遍历结果和右子树的前序遍历结果进行递归即可。终止条件是左子树或右子树只有一个值，代表一个叶节点。那么如何求左右子树的前序遍历呢？在上面的例子中，我们找到了3的左右子树的中序遍历结果，由于前序遍历是先访问左子树，所以我们在中序遍历中统计3左边的个数，并且只有一个9。那么我们习惯把中序遍历中的3,9,20,15,7在3之后压一位，那么9就是左子树前序遍历的结果，而20、15、9后的7是柚子树前序遍历的结果。最后，只需递归即可解决问题。我们将继续将输入拆解为左右子树的输入，直到达到终止条件。解决这个问题的关键不仅要知道前序遍历、中序遍历、后序遍历怎么写，还要知道前序遍历的第一个节点是根节点，后序遍历的最后一个节点是根节点，中序遍历以根节点为中心，左右分别是它的左右子树，这几个重要的扩展特征。说完reverse，我们说forward，也就是递归的二叉树。其实，除了递归之外，二叉树常用的一种遍历方法就是使用栈进行广度优先遍历。典型主题包括从上到下打印二叉树。从上到下打印一棵二叉树从上到下打印一棵二叉树是一个简单的问题。题目如下：从上到下逐层打印一棵二叉树。同一层的节点从左到右依次打印，每一层打印一行。这道题需要从左到右按顺序打印，完全遵循广度优先遍历，二叉树递归的时候我们不能急于读取值，而是按照左中右，遇到左右时子树节点，push到栈尾，使用while语句不断循环，直到栈为空。扩容时追加到栈尾，不断处理栈元素的方法非常优雅，符合栈的特性。当然，如果标题需要倒序打印，可以按右、中、左的顺序处理。接下来看深度优先遍历。典型的话题是二叉树的深度。二叉树的深度二叉树的深度是一个简单的问题。题目如下：输入一棵二叉树的根节点，求树的深度。从根节点到叶节点（包括根节点和叶节点）所经过的节点构成树的一条路径，最长路径的长度就是树的深度。由于二叉树有多个分支，我们在遍历之前不知道哪条路由最深，所以必须使用递归尝试。我们可以换个思路，用函数语义来理解。假设我们有这么一个函数deep求一棵二叉树的深度，这个函数的内容是什么？二叉树只能有左右子树，所以deep一定是左右子树的最大深度+1（自身）的最大值。求左右子树的深度，可以复用deep函数构成递归。我们只需要考虑边界情况，即访问节点不存在时，返回深度为0，所以代码如下：functiondeep(node:TreeNode){if(!node)return0returnMath.max(deep(node.left),deep(node.right))+1}从这里可以看出二叉树一般可以用更优雅的递归函数来求解，如果你的解题思路不包括递归是通常不是最优雅的解决方案。一个类似的优雅主题是平衡二叉树。平衡一棵二叉树平衡一棵二叉树是一道简单的题，题目如下：输入一棵二叉树的根节点，判断这棵树是否为平衡二叉树。如果任意一个节点的左右子树的深度差不超过1，那么一棵二叉树就是平衡二叉树。同样，我们假设函数isBalance是答案函数，那么平衡二叉树的一个特征一定是它的左右子树也是平衡的，所以可以写成：错了，左右子树的平衡不够，如果左右子树的深度差超过1，就会坏掉，所以我也求一下左右子树的深度，我们重用functiondeep在上一题中，整理如下：(root.left)-deep(root.right))<2}这个问题提醒我们并不是所有的递归都可以完美地写成一个只调用自己的模式。不同的topic需要用其他的功能来补充，我们要敏锐的意识到它还缺少什么条件。还有一种递归，不是简单的函数递归自己，而是构造另一个函数递归，因为递归的参数不同。一个典型的主题是对称二叉树。Symmetricalbinarytree对称二叉树是一道简单的题，题目如下：请实现一个判断二叉树是否对称的函数。如果二叉树与其镜像相同，则二叉树是对称的。我们应该注意到，二叉树的镜像是非常特殊的。比如最左边的节点和最右边的节点互为镜像，但是它们的父节点并不相同。因此，isSymmetric(tree)等参数不能是子递归的。解决方法是将左右子树作为参数，让它们进行相等的判断。传递参数时，只传入父节点不同但互为镜像的左右节点即可。所以我们要创建一个新函数isSymmetricNew(left,right)，比较left.left和right.right，比较left.right和right.left。具体代码就不写了，再注意边界条件。这道题的重点在于，由于镜像的关系，它们没有同一个父节点，所以必须使用一个新参数的函数进行递归。如果问题反过来呢？构建二叉树图像怎么样？二叉树的镜像二叉树的镜像是一道简单的题，题目如下：请完成一个函数，输入一棵二叉树，函数输出它的镜像。判断镜像比较容易，但是在构建镜像的时候需要考虑一下：比如输入：4/\27/\/\1369镜像输出：4/\72/\/\9631观察发现，其实镜像可以理解为左右子树的交换，同时递归交换每个子树的左右子树，构成递归:functionmirrorTree(node:TreeNode){if(node===null)returnnullconstleft=mirrorTree(node.left)constright=mirrorTree(node.right)node.left=rightnode.right=leftreturnnode}我们要从下往上走，所以先递归生成左右子树，然后进行交换当前节点，最后回到根节点。接下来介绍一些具有一定难度的经典题型。二叉树的最近共同祖先二叉树的最近共同祖先是一个中级问题。题目如下：给定一棵二叉树，找到树中两个指定节点的最近共同祖先。题目简短明了，就是找最近的共同祖先。显然，根节点是所有节点的共同祖先，但不一定是最近的。我们仍然使用递归，首先考虑特殊情况：如果任何节点等于当前节点，则当前节点必须是最近的公共祖先，因为另一个节点必须在其子节点中。那么，用递归的思路，如果我们用lowestCommonAncestor函数分别求出左右子节点的最近公共祖先呢？functionlowestCommonAncestor(node,a,b){constleft=lowestCommonAncestor(node.left)constright=lowestCommonAncestor(node.right)}如果找不到左右节点，说明当前节点是最近的公共子节点node:if(!left&&!right)returnnode如果找不到左节点，那么右节点就是答案，否则相反：if(!left)returnrightreturnleft这里巧妙地利用了函数语义来判断结果。二叉树的右视图二叉树的右视图是一个中级问题。题目如下：给定一棵二叉树，想象自己站在它的右边，按照从上到下的顺序返回从右边可以看到的节点值。.想象一束光从二叉树的右向左照射，从上往下读就是答案。其实这道题可以认为是一道融合题。右边的光束可以看成是分层照射的，所以我们用广度优先算法遍历的时候，对于每一层，我们都找到最后一个节点打印，按顺序打印就是最终的答案。有一个关于二叉树的问题。根据树的深度，按照广度优先遍历打印成二维数组。其实有一个巧妙的方法来记录树的深度，就是在栈尾添加元素的时候，添加一个depthkey，这样访问读取深度值就很自然了。完全二叉树的节点数完全二叉树的节点数是一个中等水平的问题。题目如下：给定一棵完全二叉树的根节点root，求树中节点的个数。完全二叉树的定义如下：在一棵完全二叉树中，除了最底层的节点可能未被填充外，每一层的节点数都达到最大值，并且最底层的节点全部集中在层的最左边位置。如果最底层是第h层，那么这一层包含1~2^h个节点。如果用递归来解决这个问题，关键是要分几种情况来讨论完全二叉树。由于底层可以不填充，但是底层肯定有节点，而且是从左到右填充的，那么递归遍历左边的节点就可以得到树的最大深度，我们可以快速计算通过最大深度的节点树，前提是二叉树必须是满的。但是底层节点可能不满意，怎么办？视情况而定，首先，如果一直在根据node.right....right递归获取右节点的深度，发现和最大深度一样，那么就是满二叉树,你可以直接计算结果。看一下node.right...left的深度是否等于最大深度，表示node.left，即左子树是一棵满二叉树，节点个数可以通过数学公式2^n-1。如果不等于最大深度怎么办？就是说右子树的深度减1就是一棵满二叉树。也可以通过数学公式快速计算出节点数，然后递归计算另一边。总结从题目中我们就可以感受到二叉树解题的魅力在于递归。在二叉树问题中，我们可以同时追求优雅和答案。讨论地址为：Jingdu《算法 - 二叉树》·Issue#331·dt-fe/weekly想参与讨论的请戳这里，每周都有新话题，周末或周一发布。前端精读——帮你过滤靠谱的内容。关注前端精读微信公众号
