关于前端:精读算法-二叉树

二叉树是一种数据结构，并且领有品种简单的分支，本文作为入门篇，只介绍一些根本二叉树的题型，像二叉搜寻树等等不在此篇介绍。

二叉树其实是链表的升级版，即链表同时领有两个 Next 指针，就变成了二叉树。

二叉树能够依据一些个性，比方搜寻二叉树，将查找的工夫复杂度升高为 logn，而且堆这种数据结构，也是一种非凡的二叉树，能够以 O(1) 的工夫复杂度查找最大值或者最小值。所以二叉树的变种很多，都能够很好的解决具体场景的问题。

要入门二叉树，就必须了解二叉树的三种遍历策略，别离是：前序遍历、中序遍历、后序遍历，这些都属于深度优先遍历。

所谓前中后，就是拜访节点值在什么机会，其余机会按先左后右拜访子节点。比方前序遍历，就是先拜访值，再拜访左右；后续遍历就是先拜访左右，再拜访值；中序遍历就是左，值，右。

用递归形式遍历树非常简单：

function visitTree(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 = [9,3,15,20,7]

先给你二叉树前序与中序遍历后果，让你重建二叉树，这种逆向思维的题目就难了不少。

仔细观察遍历个性能够看出，咱们兴许能揣测出一些要害节点的地位，再通过数组切割递归一下就能解题。

前序遍历第一个拜访的肯定是根节点，因而 3 肯定是根节点，而后咱们在中序遍历找到 3，这样 右边就是所有左子树的中序遍历后果，左边就是所有右子树的中序遍历后果 ，咱们只有再找到 左子树的前序遍历后果与右子树的前序遍历后果，就能够递归了，终止条件是左或右子树只有一个值，那样就代表叶子节点。

那么怎么找左右子树的前序遍历呢？下面例子中，咱们找到了 3 的左右子树的中序遍历后果，因为前序遍历优先拜访左子树，因而咱们数一下中序遍历中，3 右边的数量，只有一个 9，那么咱们从前序遍历的 3,9,20,15,7 在 3 之后推一位，那么 9 就是左子树前序遍历后果，9 前面的 20,15,7 就是柚子树的前序遍历后果。

最初只有递归一下就能解题了，咱们将输出一直拆解为左右子树的的输出，直到达到终止条件。

解决此题的要害是，不仅要直到如何写前中后序遍历，还要晓得前序遍历第一个节点是根节点，后序遍历最初一个节点是根节点，中序遍历以根节点为核心，左右别离是其左右子树，这几个重要延长特色。

说完了反向，咱们说正向，即递归一颗二叉树。

其实二叉树除了递归，还有一种常见的遍历办法是利用栈进行广度优先遍历，典型题目有从上到下打印二叉树。

从上到下打印二叉树是一道简略题，题目如下：

从上到下按层打印二叉树，同一层的节点按从左到右的程序打印，每一层打印到一行。

这道题要求从左到右程序打印，齐全遵循广度优先遍历，咱们能够在二叉树递归时，先不要急着读取值，而是依照左、中、右，遇到左右子树节点，就推入栈的开端，利用 while 语句一直循环，直到栈空为止。

利用开展时追加到栈尾，并一直循环解决栈元素的形式十分优雅，而且合乎栈的个性。

当然如果题目要求倒序打印，你就能够以右、中、左的程序进行解决。

接下来看看深度优先遍历，典型题目是二叉树的深度。

二叉树的深度是一道简略题，题目如下：

输出一棵二叉树的根节点，求该树的深度。从根节点到叶节点顺次通过的节点（含根、叶节点）造成树的一条门路，最长门路的长度为树的深度。

因为二叉树有多种分支，在遍历前，咱们并不知道哪条路线是最深的，所以必须利用递归尝试。

咱们能够转换一下思路，用函数式语义形式来了解。假如咱们有了这样一个函数 deep 来求二叉树深度，那么这个函数内容是什么呢？二叉树只可能存在左右子树，所以 deep 必然是左右子树的最大深度的最大值 +1（它本人）。

而求左右子树深度能够复用 deep 函数造成递归，咱们只须要思考边界状况，即拜访节点不存在时，返回深度 0 即可，因而代码如下：

function deep(node: TreeNode) {if (!node) return 0
  return Math.max(deep(node.left), deep(node.right)) + 1
}

从这能够看出，二叉树个别能用比拟优雅的递归函数解决，如果你的解题思路不蕴含递归，往往就不是最优雅的解法。

相似优雅的题目还有，均衡二叉树。

均衡二叉树是一道简略题，题目如下：

输出一棵二叉树的根节点，判断该树是不是均衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 1，那么它就是一棵均衡二叉树。

同理，咱们设函数 isBalance 就是答案函数，那么一个均衡二叉树的特色，必然是其左右子树也是均衡的，所以能够写成：

function isBalance(node: TreeNode) {if (root == null) return true
  return isBalance(node.left) && isBalance(node.right)
}

然而哪里不对，左右子树均衡还不够啊，万一左右子树之间深度相差超过 1 就坏了，所以还要求一下左右子树的深度，咱们复用上题的函数 deep，整顿一下如下：

function isBalance(node: TreeNode) {if (root == null) return true
  return isBalance(root.left) && isBalance(root.right) &&
    Math.abs(deep(root.left) - deep(root.right)) < 2
}

这道题揭示咱们，不是所有递归都能完满写成仅本人调用本人的模式，不同题目要辅以其余函数，要敏锐的察觉到还短少哪些条件。

还有一种递归，不是简略的函数本身递归本身，而是要结构出另一个函数进行递归，起因是递归参数不同。典型的题目有对称的二叉树。

对称的二叉树是一道简略题，题目如下：

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

咱们要留神，一颗二叉树的镜像比拟非凡，比方最左节点与最右节点互为镜像，但它们的父节点并不相同，因而 isSymmetric(tree) 这样的参数是无奈子递归的，咱们必须拆解为左右子树作为参数，让它们进行相等判断，在传参时，将父级不同，但互为镜像的左右节点传入即可。

所以咱们必须起一个新函数 isSymmetricNew(left, right)，将 left.left 与 right.right 比照，将 left.right 与 right.left 比照即可。

具体代码就不写了，而后留神一下边界状况即可。

这道题的重点是，因为镜像的关系，并不领有雷同的父节点，因而必须用一个新参数的函数进行递归。

那如果这道题反过来呢？要求结构一个二叉树镜像呢？

二叉树的镜像是一道简略题，题目如下：

请实现一个函数，输出一个二叉树，该函数输入它的镜像。

判断镜像比拟容易，但结构镜像就要想一想了：

例如输出：4
   /   \
  2     7
 / \   / \
1   3 6   9

镜像输入：4
   /   \
  7     2
 / \   / \
9   6 3   1

察看发现，其实镜像能够了解为左右子树调换，同时 其各子树的左右子树再递归调换，这就形成了一个递归：

function mirrorTree(node: TreeNode) {if (node === null) return null

  const left = mirrorTree(node.left)
  const right = mirrorTree(node.right)
  node.left = right
  node.right = left
  return node
}

咱们要从下到上，因而学生成递归好的左右子树，再进行以后节点的调换，最初返回根节点即可。

接下来介绍一些有肯定难度的经典题。

二叉树的最近公共先人是一道中等题，题目如下：

给定一个二叉树, 找到该树中两个指定节点的最近公共先人。

题目很简短，也很明确，就是寻找最近的公共先人。显然，根节点是所有节点的公共先人，但不肯定是最近的。

咱们还是用递归，先思考非凡状况：如果任意节点等于以后节点，那么以后节点肯定就是最近公共先人，因为另一个节点肯定在其子节点中。

而后，利用递归思维思考，假如咱们利用 lowestCommonAncestor 函数别离找到左右子节点的最近公共先人会怎么？

function lowestCommonAncestor(node, a, b) {const left = lowestCommonAncestor(node.left)
  const right = lowestCommonAncestor(node.right)
}

如果左右节点都找不到，阐明只可能以后节点是最近公共子节点：

if (!left && !right) return node

如果左节点找不到，则右节点就是答案，否则相同：

if (!left) return right
return left

这里奇妙利用了函数语义进行后果判断。

二叉树的右视图是一道中等题，题目如下：

给定一棵二叉树，设想本人站在它的右侧，依照从顶部到底部的程序，返回从右侧所能看到的节点值。

设想一束光照，从二叉树右侧向左照耀，自上而下读取即是答案。

其实这道题能够认为是一道交融题。右侧的光束能够认为是分层照耀的，那么当咱们用广度优先算法遍历时，对于每一层，都找到最初一个节点打印，并且按程序打印就是最终答案。

有一道二叉树的题目，是依据树的深度，依照广度优先遍历打印成二维数组，记录树的深度其实也有奇妙方法，即在栈尾追加元素时，减少一个深度 key，那么拜访时天然就能够读到深度值。

齐全二叉树的节点个数是一道中等题，题目如下：

给你一棵 齐全二叉树 的根节点 root，求出该树的节点个数。

齐全二叉树 的定义如下：在齐全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最上面一层的节点都集中在该层最右边的若干地位。若最底层为第 h 层，则该层蕴含 1 ~ 2^h 个节点。

用递归解决这道题的话，要害要分几种状况探讨齐全二叉树。

因为最底层可能没有填满，但最底层肯定有节点，而且是依照从左到右填的，那么递归遍历左节点就能够获取树的最大深度，通过最大深度咱们能够疾速计算出节点个树，前提是二叉树必须是满的。

但最底层节点可能不满，那怎么办呢？分状况即可，首先，如果始终依照 node.right....right 递归取得右侧节点深度，发现和最大深度雷同，那么就是一个满二叉树，间接计算出后果即可。

咱们再看 node.right...left 的深度如果等于最大深度，阐明 node.left 也就是左子树是个满二叉树，能够通过数学公式 2^n-1 疾速算出节点个树。

如果不等于最大深度呢？则阐明右子树深度减 1 是满二叉树，也能够通过数学公式疾速计算节点个数，再通过递归计算另一边即可。

从题目中能够感触到，二叉树的解题魅力在于递归，二叉树问题中，咱们能够同时谋求优雅与答案。

探讨地址是：精读《算法 – 二叉树》· Issue #331 · dt-fe/weekly

如果你想参加探讨，请点击这里，每周都有新的主题，周末或周一公布。前端精读 – 帮你筛选靠谱的内容。

关注 前端精读微信公众号

版权申明：自在转载 - 非商用 - 非衍生 - 放弃署名（创意共享 3.0 许可证）

精读

重建二叉树

从上到下打印二叉树

二叉树的深度

均衡二叉树

对称的二叉树

二叉树的镜像

二叉树的最近公共先人

二叉树的右视图

齐全二叉树的节点个数

总结