关于前端:前端学数据结构与算法六二叉树的四种遍历方式及其应用

前言

上一章咱们从 0 到1的实现了一颗二叉搜寻树，以及了解了二叉搜寻树的个性与基本操作，这一章介绍对于二叉树的更多操作，也就是树的遍历，对树的每个节点进行拜访。次要包含前序遍历、中序遍历、后序遍历、层序遍历，后面三种也叫深度优先遍历(DFS)，最初的层序遍历也叫广度优先遍历(BFS)，了解这四种遍历形式的不同，再遇到树相干的算法问题时，也就能更加熟能生巧。这里不单指二叉搜寻树，遍历思维同样实用于多叉树。

深度优先遍历(DFS)

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

前序遍历

也就是靠前拜访到树的节点，首先贴出代码，给上一章实现的二叉搜寻树减少前序遍历的办法：

class BST {constructor() {this.root = null // 根节点}
  ...
  
  preorder(fn) { // 前序遍历
      const _helper = node => {if (!node) {return}
      fn(node.val) // 先拜访根节点
      _helper(node.left) // 再拜访左节点
      _helper(node.right) // 最初拜访右节点
    }
    _helper(root)
  }
}

无论应用哪种遍历形式都是为了拜访到树的每个节点，留神下面代码里函数 fn 的地位，它位于两个递归函数的后面，所以叫它前序遍历；而中序遍历 fn 就是在两个递归函数的两头；后序遍历 fn 就是在两个递归函数的前面，它们叫法的由来，也是仅此而已。尽管是这么一点点的区别，然而后果相差挺大且利用形式的区别也很大，首先来看下前序遍历：

当应用前序遍历时，它的拜访程序是 15、10、7、12、26、22、37。它的拜访特点是首先拜访这棵树的根节点，而后拜访它的左子树，最初是拜访右子树，这也是看起来比拟合乎直觉的一种遍历形式。如果还是不太好了解的话，能够将一整颗树合成来了解：

因为是前序遍历，首先遇到子树 A，此时它的根节点是15，被拜访到。而后去它的左子树B，节点10 又是子树 B 的根节点，所以被拜访到。再去节点 7 与两个 null 形成的子树，节点 7 被拜访到，因为 7 的左右孩子都是null，所以返回到父节点10，最初去拜访右节点12，整棵树的左子树就拜访完了。而后再右子树履行同样的规定进行拜访。以此类推也就造成了方才看到的拜访程序后果，晓得它的拜访程序有什么用？那就以一道算法题来看其利用。

前序遍历利用 – 108- 将有序数组转换为二叉搜寻树

将一个依照升序排列的有序数组，转换为一棵高度均衡二叉搜寻树。一个高度均衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它能够示意上面这个高度均衡二叉搜寻树：0
     / \
   -3   9
   /   /
 -10  5

必须要高度均衡，所以不能呈现一边高一点低的状况。该题有个条件是在一个有序的数组汇合里，所以再重构这颗树时，根节点就能够抉择数组的两头地位，因为剩下左侧局部全副是小于根节点的，而右侧局部全副是大于根节点的，正好合乎二叉搜寻树的定义。以此类推剩下局部的根节点仍然两头地位，从而进行左右的宰割，直到最初不能进行宰割即可。

function TreeNode(val) { // 树节点类
  this.val = val;
  this.left = this.right = null;
}

var sortedArrayToBST = function (nums) {const _helper = (arr, l, r) => { // l 为左边界、r 为右边界
    if (l > r) { // 递归终止条件
      return null
    }
    const mid = l + (r - l) / 2 | 0 // 取数组两头值，并向下取整
    const node = new TreeNode(arr[mid]) // 前序遍历，实例化为树节点
    node.left = _helper(arr, l, mid - 1) // 将宰割的左侧构建为二叉搜寻树
    node.right = _helper(arr, mid + 1, r) // 将宰割的右侧构建为二叉搜寻树
    return node // 将构建好的树返回
  }
  return _helper(nums, 0, nums.length - 1) // 留神前闭后闭的区间形式
};

为什么不采纳 (l + r) / 2，而采纳l + (r - l) / 2 的书写形式，是为了防止出现整型溢出的状况。因为数组里每一项的值首先须要实例化为树的节点TreeNode，能力创立它的左孩子和右孩子，所以采纳前序遍历的形式。整棵树的构建程序也是先根节点，而后左子树，最初右子树的程序实现。

中序遍历

仅仅只是扭转了拜访节点的程序，首先拜访左子树，而后拜访以后根节点，最初拜访右子树。还是贴出代码：

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

就是简略的更改了拜访节点的地位，程序也很有意思：

后果是7、10、12、15、22、26、37，正好是一个升序排列形式，这也是二叉搜寻树应用中序遍历的一个特点，如果了解了之前前序遍历递归函数的运行过程，中序遍历了解起来就不难了。因为首先是拜访完左子树，只有左孩子不是null，递归函数就会始终往左侧拜访，而二叉搜寻树最小的节点正好最左侧的叶子节点，到了底部之后则开始采纳左中右的递归程序往回走，正好是一个升序排列。它有啥用？还是应用一个算法题来看其利用。

中序遍历利用 – 530- 二叉搜寻树的最小相对差

给你一棵所有节点为非负值的二叉搜寻树，请你计算树中任意两节点的差的绝对值的最小值。

看题目不是太好了解，就以咱们示例的二叉搜寻树为例：

依照该题的算法，解为2，因为任意两个之间的绝对值，这是最小的。一下没有想到解题的思路？没事，如果咱们把这颗二叉搜寻树看成是一个升序数组[7, 10, 12, 15, 22, 26, 37]，求解该数组任意两个值之间差的最小绝对值。不难发现其实 ” 任意 ” 是个幌子，你只能去比拟两个相连数字它们的绝对值。再去看二叉搜寻树，也就明确了，应用中序遍历，比拟两个前后拜访的节点即可失去 ” 任意 ” 两个节点的最小绝对值差。

var getMinimumDifference = function (root) {
  let prev = null // 保留之前拜访的节点
  let minimum = Infinity // 取最大值
  const _helper = node => {if (!node) {return}
    _helper(node.left)
    if (prev !== null) { // 第一次拜访没有 prev 节点
      minimum = Math.min(minimum, node.val - prev.val) // 始终保留最小的值
    }
    prev = node // 将本次循环的节点缓存为上一个节点
    _helper(node.right)
  }
  _helper(root)
  return minimum // 返回最小差
};

应用一个 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- 二叉树的所有门路

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

题目的要求是从根节点到叶子节点，所以要记录每一步的以后节点，而前序遍历的程序正好能够记录从根到叶子节点的整条门路。而这道题有意思的中央在于前序遍历返回时，须要把最初一步的叶子节点从门路里移除掉，从新增加另外的节点门路值，所以能够在后序遍历的程序里，像贪吃蛇一样一口口的去吃掉曾经拜访过的门路。有人把这种解法取了个挺厉害的名叫回溯。代码如下：

var binaryTreePaths = function (root) {const ret = []
  const _helper = (node, path) => {if (!node) {return}
    path.push(node.val) // 前序遍历拜访，记录门路的每一步
    _helper(node.left, path)
    _helper(node.right, path)
    if (!node.left && !node.right) { // 达到了叶子节点
      ret.push(path.join('->')) // 将门路转换为字符串
    }
    path.pop() // 后序遍历拜访，将拜访过的门路节点弹出}
  _helper(root, [])
  return ret
};

广度优先遍历(BFS)

深度优先是先遍历完一棵子树，再遍历完另一颗子树，而广度优先的意思是依照树的层级一层层的拜访每个节点，图示如下：

当然你也能够从右往左的打印，打印程序就是15、26、10、37、22、12、7，广度优先的实现咱们须要借助另外一种数据结构《队列》，因为一般的队列了解起来并不简单，所以之前的章节也没有独自介绍。正好到了树的层序遍历，在这里能够将队列的定义及其利用一并介绍。

什么是队列

之前的章节咱们介绍了栈，这是一种一端堵死，后进先出的数据结构。而队列则有不同，没有哪头堵死，从队尾进入，队首出队的一种程序数据结构。

这也是一种受控的数据结构，提供的接口只能拜访到队尾和队首，两头的元素内部无法访问到。

树的 BFS 实现

应用队列，将每个节点入队，同时在出队一个节点后，将它的两个孩子节点入队。首先入队根节点，而后出队根节点的同时，入队它的两个孩子节点，此时队列不为空，持续采纳同样的形式入及出队接下来的节点。

代码实现如下：

class BST {constructor() {this.root = null // 根节点}
  ...
  
  levelOrder(fn) {if (!this.root) {return}
    const queue = [this.root] // 首先入队根节点
    while (queue.length > 0) {const node = queue.shift() // 出队队首节点
      fn(node.val) // 拜访出队节点值
      if (node.left) { // 入队左孩子
        queue.push(node.left)
      }
      if (node.right) { // 入队右孩子
        queue.push(node.right)
      }
    }
  }
}

广度优先遍历利用 – 637- 二叉树的层平均值

这个齐全就是为了层序遍历而量身定制的，不过和惯例的遍历有所不同，需要求出每一层的平均值，也就是说在遍历完一层的时候，咱们须要晓得这一层曾经遍历完了，这样才能够求出平均值。能够在 while 循环内再加一个针对每一层的循环，代码如下：

var averageOfLevels = function (root) {if (root === null) {return []
  }
  const queue = [root]
  const ret = [] // 最终返回的后果
  while (queue.length > 0) {
    let len = queue.length
    let sum = 0 // 记录每一层的总和
    for (let i = 0; i < len; i++) { // 遍历每一层
      const node = queue.shift()
      sum += node.val
      if (node.left) {queue.push(node.left)
      }
      if (node.right) {queue.push(node.right)
      }
    }
    ret.push(sum / len) // 求出该层的均匀
  }
  return ret
};

最初

通知大家一个不好的音讯，以上所有题目均为简略难度。当然次要是为了相熟树的遍历形式，还有很多经典的树的问题，如树的公共先人、翻转、序列化等，再了解了树的遍历和递归后，再面对这些问题也会更好了解，本章内容只是一个抛砖引玉的作用。本章 github 源码