关于二叉树、递归、DFS、BFS

前言

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

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

树的基本概念

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

一些常见的名词解释：

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

二叉树

二叉树特点

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

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

完全二叉树：完全二叉树是由满二叉树而引出来的，若设二叉树的深度为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 , 非线性就要用到递归，你会发现只要的涉及递归的问题，都是树的问题，就算他的数据结构不是树，也能抽象为树。

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

二叉树的各种姿势

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

结点的数据结构如下

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链接

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）

平衡二叉树的定义：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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

和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等基本算法思想的基本思想及使用。
• 掌握常见二叉树题型的解法即思路。
• 文章很长，一万多字加图文，大家可以点个赞收藏一下，马了慢慢看。
• 在社区潜水这么久，很感谢掘金上的大佬们的技术分享，一路走来帮助我这个还在学校的小白学到了很多，也希望自己能写出好的文章回馈社区，总结自己最近学到的东西能帮助到一起学习的掘友们。掘金大佬如云，我这样的小白发文也是诚惶诚恐。如果我写的有啥不对的欢迎大家在评论区告诉我呀，期待和大家一起交流~🤣🤣🤣