阅读 2316

聊聊二叉树的各种姿势(递归, AVL, BST, DFS, BFS)

前言

前言:这是作为一个正在学习的前端开发者整理一下最近写的题,这篇文章是我对二叉树算法的浅显的理解,和我对一些常用算法思想的理解,希望可以让你在看完文章之后对常见的二叉树操作有一定的了解,文中列举了我觉得比较经典的一些题目。有不对的地方欢迎指出。😮😮😮

本文首发于我的博客 :alicekeke.github.io/2020/03/06/…

树的基本概念

树的定义:是一类重要的非线性数据结构,是以分支关系定义的层次结构。每个结点有零个或多个子结点;没有父结点的结点称为根结点;每一个非根结点有且只有一个父结点;除了根结点外,每个子结点可以分为多个不相交的子树

一些常见的名词解释:

  • 节点的度:一个节点含有的子树的个数称为该节点的度
  • 叶子结点:没有子节点的节点
  • 结点层次:从根开始定义起,根为第一层,根的孩子为第二层,以此类推
  • 树的深度:树中结点的最大层次数称为树的深度或高度

二叉树

二叉树特点

二叉树是每个节点最多拥有两个子节点,左子树和右子树是有顺序的不能任意颠倒。

满二叉树:在一棵二叉树中。如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。

满二叉树

完全二叉树:完全二叉树是由满二叉树而引出来的,若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树),第 h 层所有的结点都连续集中在最左边,这就是完全二叉树

完全二叉树
求解二叉树的题目,离不开递归,递归的算法框架,是很多常用算法框架的雏形;大部分算法技巧,本质上都是树的遍历问题。

关于递归

什么是递归

递归:无限调用自身这个函数,每次调用总会改动一个关键变量,直到这个关键变量达到边界的时候,不再调用。

简单来说:就是函数不断调用函数本身,就叫递归

上一张我发过朋友圈的图

递归复习

递归递归,先递过去,再归回来

就像这样,一个大的问题(复习)拆成很多子问题来解决,子问题不会又拆成子子问题...,(递)好不容易终于最小最小的那个子问题被解决了,这个最小最小的问题被解决,得到返回值,返回值又解决了上一层子问题,上一层的返回值又解决了上上一层的问题... 依次类推,直到最开始的问题被解决(归)。

所以,所以我们应该关心的是每一层递归要解决什么问题?🤔问题被解决后应当有什么返回值?🤔和当前整个递归的退出条件。

递归的误区

我刚开始写递归的题,摆脱不了用线性的for、while(true)解题方法去思考,想这一层函数做了什么,它调用完自身后的下一层函数又做了什么…这样很容易蒙 (ಥ_ಥ)),你都写递归了还把函数拆开来if else一步步迭代,这不是适得其反嘛,(/□\*)。我们其实不用关注整个递归要走多少遍,每一遍都得出什么结果。其实既然递归是给每一层做一样的事情,就不需要把自己绕进这个递归的圈里去,我们只需要关注一级递归的解决过程即可。

什么情况用递归?

通常情况下,能被递归解决的问题具有以下两个特点:

  1. 一个问题可以分解成具有相同解决思路的子问题,子子问题,换句话说这些问题都能调用同一个函数
  2. 经过层层分解的子问题最后一定是有一个不能再分解的固定值的(即终止条件),如果没有的话,就无穷无尽地分解子问题了,没有出口,死循环必定无解。

在求解递归问题之前,必须通过以上两个特点验证是否能用递归求解。 通过判断后,我们就可以使用递归的解题模板。

递归三部曲

像我上面说的,递归之前先思考三连:每一层递归要解决什么问题?问题被解决后应当有什么返回值?当前整个递归的退出条件?

总结出这个递归的基本套路

  1. 找整个递归的终止条件:递归应该在什么时候结束?
  2. 找返回值:应该给上一级什么返回值?
  3. 本级递归应该做什么:在这一级递归中,应该完成什么任务?

套用这个三步曲,我们可以解决一些常见的递归问题:

比如经典的斐波那契数列,f[n]=f[n-1]+f[n-2]。n-1是传入参数n的前一个,n-2是最后传入参数n的前两个数字,我们每次都要让f(n-1)和f(n-2)相加得出返回值,直到找到出口f(1)f(2) 返回1。套用模板明确每一步干什么:

  1. 递归的结束条件?f[1]=1,f[2]=1,就是那个最小粒度可求解的子问题,
  2. 该层给上一级返回什么信息?return f(n-1)+f(n-2)
  3. 本级递归应该完成什么任务?每层的任务都是相同的,即计算返回f[n-1]+f[n-2]。

这样就可以很简单的写出斐波那契数列的递归解法

function fn(n){
	if(n==1|n==2){
	return 1;
	}
	return fn(n-1)+fn(n-2);	
	//不断调用自身函数,n-1是传参的前一次,n-2是最后传参的前两个数字。
}
复制代码

相信看到这,你心里多多少少对递归有个大概的了解了。 在刷题时,根据数据结构的不同:线性或非线性,有不同的遍历数据的方法:线性对应循环和迭代 for(while), true/false , 非线性就要用到递归,你会发现只要的涉及递归的问题,都是树的问题,就算他的数据结构不是树,也能抽象为树。

先从最简单的题开始了解二叉树和递归吧。

二叉树的各种姿势

树的节点那么多,但树的节点结构都是一样的,无论多少个节点,我们可以对一个节点干的事也是一样的,如图:

TreeNode

结点的数据结构如下

 function TreeNode(val) {
 this.val = val;
 this.left = this.right = null;
 }
复制代码

根据递归设计出二叉树算法的普适方法,明确一个结点要做的事情,剩下的交给这个通用方法。

基本上所有的树都可以抽象成这样

var traverse = function(root) {
	//这里写root要做什么,具体的代码
	//剩下节点怎么办,交给同一个方法。
	traverse (root.left)
	traverse (root.right)
}
复制代码

树的遍历有很明显的分治的思想,因为很常见这样的代码👇

	traverse (root.left)	//看左边
	traverse (root.right)	//看右边
复制代码

二叉树的所有问题都可以被分成看左边(左树)和看右边(右树)两种情况,逐个解决。 类似于我们常见的二分(low,high)也是像这样把问题分成一半一半来求解。直到被分割的规模缩小到容易解决。

一些常见的二叉树算法题

先来一个最简单的😏

怎样把二叉树的所有结点加一

var plusOne= function(root) {
	if (root === null) return;
	root.val += 1;	//当前root要做的操作
	plusOne (root.left);
	plusOne (root.right);
}
复制代码

就是这样对左右树轮到的节点做一样的加一操作,树空(null)退出循环。

以下题目都是LeetCode原题,我只对题目做简单描述,推荐点我贴的链接去LeetCode看原题题目。

比较两个树是否相等

LeetCode链接

var isSameTree = function(p, q) {
  if(!p && !q) return  true;	//都为空,显然相同
  if(!p || !q) return  false;	//一个为空,一个非空,不同步,显然不同
  if(q.val !== p.val) return  false;	//结点value不一样,不同
//上面即要对每个节点做的操作,返回值是true|false,接下来就是递归判断左右树
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); //p,q 两个子树,分别比较两个子树
};
复制代码

这个树的相等性判断不需要改变树的value,只需要把所有让树不相等的情况列出,排除返回false,最后返回一个boolean值即可。

二叉树的镜像

LeetCode链接

套用解题模板:

  1. 找终止条件。 什么情况下递归结束?树为空(null),递归结束。
  2. 找返回值。 应该返回什么?返回当前交换左右子树后的节点
  3. 本级递归应该做什么。 交换后重置当前的左右子树,即调用同一个交换函数,返回交换后的节点,重置原二叉树。
var mirrorTree = function(root) {
// 交换当前节点的左右节点,再递归的交换当前节点的左节点,递归的交换当前节点的右节点 null返回
    if(!root) return null
    //交换结点
    let temp = root.left
    root.left = root.right
    root.right = temp
    // 重复对左右子树做一样的操作,并重置root
    root.left = mirrorTree(root.left)
    root.right = mirrorTree(root.right)

    return root
};
复制代码

求二叉树最大深度

LeetCode链接

套用解题模板:

  1. 找终止条件。 什么情况下递归结束?树为空(null),递归结束。
  2. 找返回值。 应该返回什么?题目求的是树的最大深度,我们需要根据每一层遍历到的深度+1,返回左右子树的深度最大值。
  3. 本级递归应该做什么。 首先,还是强调要走出之前的思维误区,每个节点就三个可操作的值:root、root.left、root.right,其中根据第二步,left和right分别记录的是root的左右子树的最大深度。我们在每一次遍历到新的节点更新这个值,然后再返回left和right中较大的那个深度即可。
var maxDepth = function(root) {
	if(root === null){
		return  0;
	}
	let lefth = maxDepth(root.left)
	let righth = maxDepth(root.right)
	return  Math.max(lefth, righth) + 1
};
复制代码

这个时候我们发现,上面这两题都只有一个返回值,并且这个返回值在遍历节点的过程中一直在更新,如果二叉树涉及到全局的变量,比如最短、最优,不止判断当前单个的二叉树节点,而是判断全局二叉树是否满足某条件,return一个返回值明显不够的,现在该怎么办呢?

借助 helpFunction

helpFunction 是将功能独立出来的一个函数,在题目较为复杂时,一个返回值不能满足我们的需求,我们需要多一些变量来记录当前的值,来保证这个值能在相对于全局而固定,不会在每一次遍历结点时被更新。

这个时候就需要helpFunction来增加参数列表,定义返回值接口,在返回值中携带更多有用的信息。

这个概念类似于函数式编程中的组合参数,它能将一个函数调用的输出路由到另一个函数的调用上,然后一直进行下去。是一种声明式抽象,以获取更多的信息

验证平衡二叉树

LeetCode链接

最典型的是104题 验证平衡二叉树(Balanced Binary Tree简称AVL)

BSTandAVL

平衡二叉树的定义: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

这个时候我们光记录当前的高度已经不够了,因为它不仅仅要求我们当前左右子树高度差不超过1,整个树的高度差都不能超过1。

所以我们至少需要两个返回值:

  1. 当前结点高度
  2. 当前结点是否是平衡二叉树

如果当前结点不是平衡二叉树,那剩下的还遍历个啥 = = ,直接返回false就行了

   var isBalanced = function (root) {
      // 传任意结点,返回当前节点的高度
      function height(node) {
        if (node === null) {
          return 0; //叶子结点,返回null
        }
        let h = Math.max(height(node.left), height(node.right)) + 1; //递归 在左右子树选较大高度值,加一即当前结点高度
        return h;
      }
      if (!root) return true; //该树没有任何叶子结点,即为平衡二叉树
      // 判断高度差绝对值是否超过1,且要递归判断每个节点的子树
      return Math.abs(height(root.left) - height(root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right)
    };
复制代码

这里用到的height函数就是helpFunction。 helpFunction根据你具体要做的事命名。宏观上它的作用就是提供更多有用参数的辅助函数。

为了理解helpFunction的作用,我们来看更多的实现场景:

二叉树的层次遍历

LeetCode链接

题目描述:给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如

    3
   / \
  9  20
    /  \
   15   7
   
  返回[ [3],[9,20],  [15,7] ]
复制代码

这里很明显需要借助helpFunction,因为我们最后返回的肯定是一个二维数组,但当前遍历是按层次遍历,节点自身只能操作自己的左右子树,所以必然需要一个函数来记录当前层次的节点,保存为一维数组;记录当前的层数与总层数比较,来向下进级。

//二叉树的层次遍历
var levelOrder = function(root) {
  let levels = []	//最后返回总的二维数组
  if(!root) {
    return levels	//空树返回空数组
  }
  function walk(node, level) {
    if(levels.length === level) {//新的层级
      levels.push([])
    }
    levels[level].push(node.val)	//保存当前结点
    if(node.left) {
      walk(node.left, level + 1)	//level+1 向下层遍历
    }
    if(node.right) {
      walk(node.right, level + 1)
    }
  }
  walk(root, 0)
  return levels;
}
复制代码

判断二叉搜索树(BST)

LeetCode链接

二叉搜索树(简称BST)是很常用的二叉树,其定义是:一个二叉树中,任意节点的值要大于左子树所有结点的值,且要小于等于右边子树所有结点的值: 如图就是应该符合定义的BST

BST

和AVL树同理,当前结点root要做的不仅仅是左右结点比较,而是整个左子树和右子树所有结点进行比较,单单一个返回值肯定不够了,这个时候就要设计一个helpFunction

var isValidBST = function (root) {
	let inOrderList = [];

	function inOrder(node) {
		if (!node) return;
		inOrder(node.left);	//判断左树
		inOrderList.push(node.val);
		inOrder(node.right);  //判断右树
	}
	// 从根节点开始遍历 返回结点数组
	inOrder(root)
	for (let i = 0; i < inOrderList.length - 1; i++) {
		// 确保遍历出的结点是递增 ==> 平衡树
		if (inOrderList[i] >= inOrderList[i + 1]) { //考虑结点相等的情况!
		return  false
		}
	}
return  true
};
复制代码

小结

看到这里,你应该学会以下几个技巧

  1. 二叉树算法的原则,把当前节点要做的事做好,其他交给递归框架,不用当前节点操心
  2. 如果当前节点会对下面的子节点有整体影响,可以通过helpFunction辅助函数设计返回值接口,携带更多的参数传递信息。
  3. BST和AVL树的验证方法

引申BFS 和 DFS

前文中我说过:任何非线性的数据结构,涉及到递归的问题,都是树的问题,就算他的数据结构不是树,也能抽象为树。接下来,我们就稍稍讨论下按深度优先和广度优先求解图的问题,同样的思想,同样的方法。

深度优先策略

首先明确下概念

深度优先搜索算法(Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

来源wiki 深度优先搜索

回溯法:是一种选优搜索法,又称为试探法

在危险的边缘疯狂试探
试探之后

关键在于,不合适就退回上一步

回溯法常见的解题模板

result = []
function backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 of 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
复制代码

但与此同时,最坏的情况下,回溯的时间复杂度会变大,所以要用到剪枝来提速。剪枝就是在搜索过程中利用过滤条件来剪去完全不用考虑(已经判断这条路走下去得不到最优解)的搜索路径,从而避免了一些不必要的搜索。剪枝这个形容非常的形象,想象一下,春天来了 花匠大叔会把树向下长的枝干全部剪掉,留下向上的。这就是剪枝。

如果具体问解的个数,问最优、最先、最短,一般来讲用dp来做,问所有的解的集合 就用DFS

DFS模板

result: 所有结果集
list: 当前的单个解	(result和list会在DFS的过程中不断更新)
pos:记录当前处理的位置
visited:结点有无访问状态(求最优路径)
if(condition) 退出条件
复制代码

举一道medium难度的dfs题做例子

所有合法括号集合

LeetCode链接

题目描述:设计一种算法,打印n对括号的所有合法的(例如,开闭一一对应)组合。且解集不能包含重复的子集。 例如,给出 n = 3,生成结果为:

[ "((()))", "(()())", "(())()", "()(())","()()()" ]

这题很明显要返回所有有效括号的解的集合,helpFuncton (题解中的DFS)要返回的返回值接口包括(当前剩余的左括号,剩余的右括号,当前加入合法的左/右括号,结果的集合)。并且只有两种情况,加入当前list或者不加.

感谢评论里掘友的意见,我画出了所有的有效情况,希望这样可以帮助大家理解。画的有点丑,大家多多包涵😥😥😥

function dfs(left, right, list, result){
	if(left === 0 && right === 0){ // 左右括号都为0,退出条件
		result.push(list)
	}
	// dfs只有两种情况,加入list或不加,提前判断加入括号是否有效
	if(left > 0){ //左括号无所谓增加 有就放
		dfs(left - 1, right, list + '(', result) //放入哪边括号 剩余n -1
	}

	//已有的左括号>右括号才能放入,即剩下的左括号<右括号
	if(left < right){
		dfs(left, right - 1, list + ')', result)
	}
}
var generateParenthesis = function(n) {
	let result = [];
	let list = '';
	// 已知n,不需要记录当前visited来判断退出条件
	dfs(n, n, '', result);
	return result;
};
复制代码

这题因为给出了终止条件,即n对括号,凑满了就不用再判断,所以不需要记录判断当前visited。

并且这里在判断valid时用到剪枝的思想:因为有些DFS是把所有情况的解都产生之后,在判断退出条件的时候再判断是否valid;

但我们在加入当前list之前就判断左右括号是否valid,满足才放进result,这样就保证在长度(n)合适退出循环的时候,拿到的result都是有效的解。

广度优先策略

BFS: 从根节点出发,沿着树的宽度,每次都访问同一层的节点,若同一层都访问完,再访问下一层,若所有的节点均被访问,则算法终止,最后BFS找到的路径即为最短路径。

BFS相对于DFS,DFS是一条路走到底,没有先后顺序,BFS按层级遍历,好记录当前遍历层级,更利于求最优路径。

腐烂的橘子

LeetCode链接

题目描述:在给定的网格中,可能有三个值:0 代表空单元格; 1 代表新鲜橘子; 2 代表腐烂的橘子。 每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。

腐烂的橘子应该是N皇后问题的简易版,这里不需要返回解集,求最小time,并且每个橘子都朝着每层的四个方向腐烂,层级优先,考虑BFS

没有用到递归。plan:枚举 + BFS

解读一下题目,映射到BFS的概念上:

  • 四个方向相邻 ——> 访问同一层节点
  • 污染四个方向上的节点 ——> 对每个坏橘为基进行BFS
  • 最短路径 ——> 最短腐烂时间

还是原来的那个模板,

result: 所有结果集
list: 当前的单个解	(result和list会在DFS的过程中不断更新)
pos:记录当前处理的位置
visited:结点有无访问状态(求最优路径)
if(condition) 退出条件
复制代码

list记录当前坏橘的坐标和最后需要返回的经过时间,二维坐标记录当前要前进的方向

var orangesRotting = function(grid) {
	// 1. 初始化坏橘坐标,好橘个数,经过时间,
	let time = 0;
	let result = [];
	let foc = 0; //fresh orange count = 0
	for(let i=0; i<grid.length; i++){
	for(let j=0; j<grid[i].length; j++){
		if(grid[i][j] === 2) result.push([i, j ,0])
		if(grid[i][j] === 1) foc++;
		}
	}
	console.log(result, foc)
	// 开始遍历队列中的坏橘
	while(result.length){
		let cur = result.shift();
		console.log(cur)
		time = cur[2];//腐烂时间
		rotting(cur[0], cur[1], cur[2]);
	}
	// 处理腐烂感染过程
	function rotting(row, col, time){
		let direction = [[-1,0], [0,1], [1,0], [0,-1]]; //先四	个方向(广度)遍历
		for(let d=0; d<4; d++){
		let r = row + direction[d][0];
		let c = col + direction[d][1]; //当前坐标向四个方向移动
		// 在gird内且是新鲜可感染的橘子,置2; 否则continue
		if(r<0 || r>=grid.length || c<0 || c>=grid[0].length || grid[r][c] !== 1) {continue} else {
		grid[r][c] = 2;
		foc --;
		result.push([r, c, time+1])
		}
	}
}
// 最后所有橘子都一定会坏,否则就没有坏橘
return foc > 0 ? -1 : time
};
复制代码

总结

  • 看完本文你将会了解递归、分治、剪枝、回溯、枚举、DFS、BFS等基本算法思想的基本思想及使用。
  • 掌握常见二叉树题型的解法即思路。
  • 文章很长,一万多字加图文,大家可以点个赞收藏一下,马了慢慢看。
  • 在社区潜水这么久,很感谢掘金上的大佬们的技术分享,一路走来帮助我这个还在学校的小白学到了很多,也希望自己能写出好的文章回馈社区,总结自己最近学到的东西能帮助到一起学习的掘友们。掘金大佬如云,我这样的小白发文也是诚惶诚恐。如果我写的有啥不对的欢迎大家在评论区告诉我呀,期待和大家一起交流~🤣🤣🤣
关注下面的标签,发现更多相似文章
评论