一、LeetCode 104. 二叉树的最大深度
题目介绍：
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
3 / \ 9 20 / \ 15 7
返回它的最大深度 3 。
方案一：DFS 深度优先查找
DFS是在树中遍历节点经常使用的一种方式 - 深度优先查找。
/** * @method maxDepthByDFS * @description: 深度优先查找 - DFS * @param {TreeNode} root * @return {*} */ function maxDepthByDFS(root: TreeNode | null): number { // 临界点条件 if (root === null) { return 0; } // 当root存在时，分别获取下左侧节点的深度、右侧节点深度 let leftDepLength = 1 + maxDepthByDFS(root.left); let rightDepLength = 1 + maxDepthByDFS(root.right); // 比较二者的最大值 return Math.max(leftDepLength, rightDepLength); }
提交代码，看下效果~
网络异常，图片无法展示
|
方案二：BFS 广度优先遍历
在遍历树的节点时，从横向上看，每一层都表示了树的深度。假定我们把横向的元素，依次放入数组队列中，每一次都放一层，只要我们遍历队列，每遍历依次就表示深度+1。
/** * @method maxDepthByBFS * @description: 广度优先查找 - BFS * @param {TreeNode | null} root * @return {number} */ function maxDepthByBFS(root: TreeNode | null): number { // 临界点条件 if (root === null) { return 0; } // 定义队列存储节点的值 - 存储每一层的节点 const queue = [root]; // 记录树深度 let depLength = 0; // 当队列中存在元素是，表示有一层 while (queue.length) { // 获取当前队列中，指向当前层所有元素的长度 const currentLevelLength = queue.length; // 将当前层元素依次出队 for (let i = 0; i < currentLevelLength; i++) { // 获取队列的第一个元素 const node = queue.shift(); // 如果left节点存在，在队列中压入 if (node?.left) { queue.push(node.left); } // 如果left节点存在，在队列中压入 if (node?.right) { queue.push(node.right); } } // 每遍历依次都代表了一层 depLength++; } // 返回结果即可 return depLength; }
结语
了解DFS和BFS区别以及使用方式.
