学习了树的深度优先算法和广度优先算法后,做这两道题就没有难度了~
一、104. 二叉树的最大深度
1、解题思路:
(1)用上一话的树的深度优先遍历算法实现
JavaScript实现树的深度优先遍历和广度优先遍历
(2)记得用一个变量去记录层级,递归刷新层级并拿最大的结果
2、编码实现
/** * @param {TreeNode} root * @return {number} */ var maxDepth = function(root) { // 深度优先遍历 let resDepth = 0; const dfs = (node, dep) => { if(!node) return; resDepth = Math.max(resDepth, dep); dfs(node.left, dep + 1); dfs(node.right, dep + 1); } dfs(root, 1); return resDepth; };
3、提交结果
二、111. 二叉树的最小深度
1、描述
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
2、解题思路
利用树的广度优先算法实现
遇到叶子结点就直接返回结果,不遍历了
因为广度优先遍历是一层一层的去遍历的,同一层找到叶子结点就返回了,所以返回的是最小深度
3、编码实现
这里跟之前广度优先算法不同的是,队列里面放的不是一个个结点,而是一个个数组,数组里面是[结点,深度]这样的形式
/** * @param {TreeNode} root * @return {number} */ var minDepth = function(root) { // 广度优先遍历 if(!root) return 0; // 这个queue里面放的元素是一个个数组 // 而数组第一个就是当前结点,初始化是root结点 // 由于要记录深度,所以第二个用来放depth,初始化是1 const queue = [[root, 1]]; while(queue.length) { // 注意这里的解构赋值 const [node, depth] = queue.shift(); if(!node.left && !node.right) return depth; if(node.left) queue.push([node.left, depth + 1]); if(node.right) queue.push([node.right, depth + 1]); } return depth; };
4、结果
写完啦~简单练手题