深度优先遍历 DFS
解题思路
终止条件：访问到叶子节点返回 0；
递归主体：
- 当 root 节点左右孩子都为空时，返回 1；
- 当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度；
- 当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值；
复杂度
-
时间复杂度：
O(N)，其中 N 是树的节点数，对每个节点访问一次； -
空间复杂度：
O(H)，其中 H 是树的高度，空间复杂度主要取决于递归时栈空间的开销；- 最坏情况下，树呈现链状，空间复杂度为
O(N)； - 平均情况下树的高度与节点数的对数正相关，空间复杂度为
O(logN)；
- 最坏情况下，树呈现链状，空间复杂度为
代码实现
var minDepth = function (root) {
if (root === null) return 0;
// 1. 左右子节点都为空，则是叶子节点，返回 1（此行代码可以省略，方便理解这里不省略）
if (root.left === null && root.right === null) return 1;
// 2. 左节点为空，只有右节点时，递归计算右节点
if (root.left === null) return 1 + minDepth(root.right);
// 3. 右节点为空，只有左节点时，递归计算左节点
if (root.right === null) return 1 + minDepth(root.left);
// 4. 左右节点都存在，都需要递归
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};
广度优先遍历 BFS
解题思路
使用层序遍历二叉树，一层一层的来遍历二叉树，当找到一个叶子节点时，直接返回这个叶子节点的深度；
广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小；
复杂度
-
时间复杂度：
O(N)，其中 N 是树的节点数，对每个节点访问一次； -
空间复杂度：
O(N)，其中 N 是树的节点数，空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数；
代码实现
var minDepth = function (root) {
if (root == null) return 0;
let queue = [root];
let depth = 1; // 深度
while (queue.length) {
let len = queue.length;
while (len--) {
let curr = queue.shift();
// 判断是当前否是叶子节点
if (curr.left == null && curr.right == null) return depth;
// 将当前节点的左右节点放入队列中
if (curr.left) queue.push(curr.left);
if (curr.right) queue.push(curr.right);
}
depth++;
}
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 104. 二叉树的最大深度
上一篇
评论
