☘️四、leetcode经典题目剖析
接下来我们引用几道经典的 leetcode 算法，来巩固树和二叉树的知识。
1、leetcode104二叉树的最大深度（简单）
（1）题意
附上题目链接：leetcode104二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
输入输出示例：
- 输入: 给定二叉树
[3,9,20,null,null,15,7] - 输出: 3
（2）解题思路
- 求最大深度，考虑使用深度优先遍历。
- 在深度优先遍历过程中，记录每个节点所在的层级，找出最大的层级即可。
（3）解题步骤
- 新建一个变量，记录最大深度。
- 深度优先遍历整棵树，并记录每个节点的层级，同时不断刷新最大深度的这个变量。
- 遍历结束返回最大深度的变量。
（4）代码实现
/** * @param {TreeNode} root * @return {number} */ let maxDepth = function(root) { let res = 0; const dfs = (n, l) => { if(!n){ return; } if(!n.left && !n.right){ res = Math.max(res, l); } dfs(n.left, l + 1); dfs(n.right, l + 1); } dfs(root, 1); return res; } 复制代码
2、leetcode111二叉树的最小深度（简单）
（1）题意
附上题目链接：leetcode111二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
**说明：**叶子节点是指没有子节点的节点。
输入输出示例：
- 输入: root =
[3,9,20,null,null,15,7] - 输出: 2
（2）解题思路
- 求最小深度，考虑使用广度优先遍历。
- 在广度优先遍历过程中，遇到叶子节点，停止遍历，返回节点层级。
（3）解题步骤
- 广度优先遍历整棵树，并记录每个节点的层级。
- 遇到叶子节点，返回节点层级，停止遍历。
（4）代码实现
/** * @param {TreeNode} root * @return {number} */ let minDepth = function(root){ if(!root){ return 0; } const q = [[root, 1]]; while(q.length){ const [n, l] = q.shift(); if(!n.left && !n.right){ return l; } if(n.left){ q.push([n.left, l + 1]); } if(n.right){ q.push([n.right, l + 1]); } } } 复制代码
3、leetcode102二叉树的层序遍历（中等）
（1）题意
附上题目链接：leetcode102二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
输入输出示例：
- 输入: 二叉树：
[3,9,20,null,null,15,7]
3 / \ 9 20 / \ 15 7 复制代码
- 输出:
[ [3], [9,20], [15,7] ] 复制代码
（2）解题思路
- 层序遍历顺序就是广度优先遍历。
- 不过在遍历时候需要记录当前节点所处的层级，方便将其添加到不同的数组中。
（3）解题步骤
- 广度优先遍历二叉树。
- 遍历过程中，记录每个节点的层级，并将其添加到不同的数组中。
（4）代码实现
/** * @param {TreeNode} root * @return {number[][]} */ // 方法一 let levelOrder1 = function(root) { if(!root){ return []; } const q = [[root, 0]]; const res = []; while(q.length){ const [n, level] = q.shift(); if(!res[level]){ // 没有该层次的数组时先创建一个数组 res.push([n.val]); }else{ // 有数组时直接将值放进 res[level].push(n.val); } if(n.left){ q.push([n.left, level + 1]); } if(n.right){ q.push([n.right, level + 1]); } } return res; }; // 方法二 let levelOrder2 = function(root){ if(!root){ return []; } const q = [root]; const res = []; while(q.length){ let len = q.length; res.push([]); while(len--){ const n = q.shift(); res[res.length - 1].push(n.val); if(n.left){ q.push(n.left); } if(n.right){ q.push(n.right); } } } return res; } 复制代码
4、leetcode94二叉树的中序遍历（简单）
（1）题意
附上题目链接：leetcode94二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
输入输出示例：
- 输入: root =
[1,null,2,3] - 输出:
[1,3,2]
（2）解题思路&&解题步骤
- 这里的解题思路和步骤和上方讲中序遍历时类似，所以不再做讲解，下面直接看代码实现。
（3）代码实现
/** * @param {TreeNode} root * @return {number[]} */ // 遍历版本 let inorderTraversal1 = function(root) { const res = []; const rec = (n) => { if(!n){ return; } rec(n.left); rec(n.val); rec(n.right); } rec(root); return res; }; // 迭代版本——栈方法 let inorderTraversal2 = function(root){ const res = []; const stack = []; let p = root; while(stack.length || p){ while(p){ stack.push(p); p = p.left; } const n = stack.pop(); res.push(n.val); p = n.right; } return res; } inorderTraversal1(root); inorderTraversal2(root); 复制代码
5、leetcode112路径总和（简单）
（1）题意
附上题目链接：leetcode112路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
输入输出示例：
- 输入:
root= [5,4,8,11,null,13,4,7,2,null,null,null,1],targetSum= 22 - 输出: true
（2）解题思路
- 在深度优先遍历的过程中，记录当前路径思维节点值的和。
- 在叶子节点处，判断当前路径的节点值的和是否等于目标值。
（3）解题步骤
- 深度优先遍历二叉树，在叶子节点处，判断当前路径路径的节点值的和是否等于目标值，是就返回true。
- 遍历结束，如果没有匹配，就返回false。
（4）代码实现
/** * @param {TreeNode} root * @param {number} targetSum * @return {boolean} */ // 递归法 let hasPathSum = function(root, targetSum) { if(!root){ return false; } let res = false; const dfs = (n, s) => { if(!n.left && !n.right && s === targetSum){ res = true; } if(n.left){ dfs(n.left, s + n.left.val); } if(n.right){ dfs(n.right, s + n.right.val); } } dfs(root, root.val); return res; }; 复制代码
6、leetcode129求根节点到叶节点数字之和（中等）
（1）题意
附上题目链接：leetcode129求根节点到叶节点数字之和
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
输入输出示例：
- 输入: root = [1,2,3]
- 输出: 25
- 解释:
- 从根到叶子节点路径 1->2 代表数字 12
- 从根到叶子节点路径 1->3 代表数字 13
- 因此，数字总和 = 12 + 13 = 25
（2）解题思路
- 在深度优先遍历的过程中，记录当前路径前面节点的值。
- 在叶子节点处，计算出当前路径值。
（3）解题步骤
- 深度优先遍历二叉树，直到每一棵树的叶子节点处结束。
- 遍历结束，返回所有路径值。
（4）代码实现
/** * @param {TreeNode} root * @return {number} */ var sumNumbers = function(root) { // 深度优先遍历处理 const dfs = (n, preNum) => { if(!n){ return 0; } const sum = preNum * 10 + n.val; if(!n.left && !n.right){ return sum; }else{ return dfs(n.left, sum) + dfs(n.right, sum); } } return dfs(root, 0); }; 复制代码
🎄五、前端与树：遍历JSON的所有节点值
1、碎碎念
有时候，后端传过来的数据可能不是很友好，有可能一串数据里面又是对象又是数组的，这个时候前端拿到数据后，就需要稍微处理一下了。
因此，我们可以通过深度优先遍历来遍历 JSON 中的所有节点值。
接下来用一个例子来展示~
2、代码实现
（1）制造数据
假设我们心在有一串 json 的数据，代码如下：
const json = { a:{ b:{ c:1 } }, d:[1, 2] } 复制代码
（2）遍历节点值
接下来，我们用深度优先遍历的方式，来遍历 JSON 中的所有节点值。具体实现代码如下：
const dfs = (n, path) => { console.log(n, path); Object.keys(n).forEach(k => { dfs(n[k], path.concat(k)); }); }; dfs(json, []); 复制代码
（3）打印结果
最终打印结果如下：
{ a: { b: { c: 1 } }, d: [ 1, 2 ] } [] { b: { c: 1 } } [ 'a' ] { c: 1 } [ 'a', 'b' ] 1 [ 'a', 'b', 'c' ] [ 1, 2 ] [ 'd' ] 1 [ 'd', '0' ] 2 [ 'd', '1' ] 复制代码
大家看上面的打印结果可以发现，通过深度优先遍历的方式，数据都被一一遍历出来。因此，对于树这种数据结构来说，在前端当中出现的频率也是较高的~~
🏡六、结束语
通过上文的学习，我们了解了树的两种遍历：深度优先遍历和广度优先遍历。同时，还有一种特殊的树，二叉树。二叉树在面试中，基本上是一大必考点。对于二叉树来说，要了解它的三种遍历方式：先序、中序和后序遍历，并且要掌握好这三者之间的区别以及常见的应用场景。
关于树在前端中的应用讲到这里就结束啦！希望对大家有帮助~
