精读

 

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

 

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

 

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

 

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

 

}

 

从这可以看出，二叉树一般能用比较优雅的递归函数解决，如果你的解题思路不包含递归，往往就不是最优雅的解法。

 

类似优雅的题目还有，平衡二叉树。