当前位置:网站首页>二叉树的四种遍历方应用

二叉树的四种遍历方应用

2020-11-08 15:22:32 osc_03803522

前言

上一章我们从01的实现了一颗二叉搜索树,以及理解了二叉搜索树的特性与基本操作,这一章介绍关于二叉树的更多操作,也就是树的遍历,对树的每个节点进行访问。主要包括前序遍历、中序遍历、后序遍历、层序遍历,前面三种也叫深度优先遍历(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-二叉树的所有路径

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


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

 

版权声明
本文为[osc_03803522]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4797210/blog/4708210