二叉树的四种遍历方应用

想让APP和微信一样，可以流畅运行小程序？ | 体验即送大疆、华为、樱桃键盘！>>>

前言

上一章我们从0到1的实现了一颗二叉搜索树，以及理解了二叉搜索树的特性与基本操作，这一章介绍关于二叉树的更多操作，也就是树的遍历，对树的每个节点进行访问。主要包括前序遍历、中序遍历、后序遍历、层序遍历，前面三种也叫深度优先遍历(DFS)，最后的层序遍历也叫广度优先遍历(BFS)，理解这四种遍历方式的不同，再遇到树相关的算法问题时，也就能更加游刃有余。这里不单指二叉搜索树，遍历思想同样适用于多叉树。

深度优先遍历(DFS)

深度优先顾名思义，首先从树的深度开始，也就是优先访问完其中一棵子树，然后再去访问另一颗子树。树的深度优先里又分为前/中/后序遍历，它们的区别仅仅是当访问到具体的节点时，它们先后顺序的不同。深度优先一般都是采用递归的方式实现，因为好理解，当然也可以使用遍历实现，不过那样会增加代码复杂性以及代码的语义化。(LeetCode上后序遍历的非递归实现可是困难难度)

前序遍历

也就是靠前访问到树的节点，首先贴出代码，给上一章实现的二叉搜索树增加前序遍历的方法：

 

使用一个prev变量缓存上一次访问的节点，每一次让当前访问到的节点值减去之前节点的值，因为是中序遍历，所以当前节点的值一定是大于之前节点的，将整颗树遍历完，返回两两相减最小的值即可。

后序遍历

也是仅仅改变访问节点的位置即可，先访问左子树，再访问右子树，最后访问自身根节点，贴代码：

class BST {
  constructor() {
    this.root = null // 根节点
  }
  ...
  
  postorder(fn) { // 后序遍历
  	const _helper = node => {
      if (!node) {
        return
      }
      _helper(node.left) // 先访问左孩子
      _helper(node.right) // 然后访问右孩子
	  fn(node.val) // 最后访问根节点      
    }
    _helper(root)
  }
}

先访问完左子树，然后是右子树，最后是自身节点，访问顺序如下： 

后序遍历应用 - 563-二叉树的坡度

给定一个二叉树，计算整个树的坡度。
一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。

简单来说就是每个节点的坡度等于它左右子树和的绝对差，所以叶子节点的坡度就是0，因为左右孩子都是空节点，返回的就是0-0的值。进行子问题拆解的话，可以理解为整颗树的坡度就是它的左右子树坡度之和，所以需要先求出左右孩子的坡度才能计算出当前节点的坡度，后序遍历非常适合。 
解题代码如下：

var findTilt = function (root) {
  let tilt = 0
  const _helper = (node) => {
    if (!node) {
      return 0 // 叶子节点的坡度为0
    }
    const l = _helper(node.left) // 先求出左子树的和
    const r = _helper(node.right) // 再求出右子树的和
    tilt += Math.abs(l - r) // 当前节点的坡度等于左右子树和的绝对差
    return l + r + node.val // 返回子树和
  }
  _helper(root)
  return tilt
};

深度优先遍历(DFS)应用进阶

以上三道算法题，分别展示了树的前/中/后序遍历的实际应用，这些还远远不够。有的算法题常规的遍历方式并不能太好解决问题，这个时候就需要在深刻理解了树的(DFS)遍历特性后，进行额外灵活的处理来解决。

反常规中序遍历 - 538-把二叉搜索树转换为累加树

给定一个二叉搜索树，把它转换成为累加树，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

题目不好懂，不过从转换的示例可以看出，从右子树最右叶子节点开始，进行两两的节点值累加，最终从右到左的累加完整棵树。如果把这颗二叉搜索树看成是一个数组[7,10,12,15,22,26,37]，那么它的操作就是数组从后往前的进行两两相加并覆盖前一个值。对于树的话，我们就需要进行反常规的中序遍历，首先遍历右子树，然后遍历根节点，最后遍历左子树，也就是进行一次降序遍历。

var convertBST = function (root) {
  let sum = 0
  const _helper = (node) => {
    if (!node) {
      return null
    }
    _helper(node.right) // 先遍历右子树
    node.val += sum // 右子树到底后逐个节点进行值的累加与覆盖
    sum = node.val // 记录的就是上个被覆盖节点的值
    _helper(node.left) // 最后遍历左子树
  }
  _helper(root)
  return root // 返回新的累加树
};

前序加后序遍历 - 257-二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。

题目的要求是从根节点到叶子节点，所以要记录每一步的当前节点，而前序遍历的顺序正好可以记录从根到叶子节点的整条路径。而这道题有意思的地方在于前序遍历返回时，需要把最后一步的叶子节点从路径里移除掉，重新添加另外的节点路径值，所以可以在后序遍历的顺序里，像贪吃蛇一样一口口的去吃掉已经访问过的路径。有人把这种解法取了个挺厉害的名叫回溯。代码如下：