Open
Description
方法一:广度优先遍历
解题思想:
在广度优先遍历过程中,如果遇到叶子节点,停止遍历,返回节点层级。
- 广度优先遍历整棵树,并记录每个节点的层级
- 遇到叶子节点,返回节点层级,停止遍历
代码:
var minDepth = function(root) {
if (!root) return 0;
// 广度优先需要使用一个队列,同时额外再维护一个深度
const q = [[root, 1]];
while (q.length) {
const [n, deepth] = q.shift();
if (!n.left && !n.right) return deepth;
// console.log(n.val, deepth);
if (n.left) q.push([n.left, deepth + 1]);
if (n.right) q.push([n.right, deepth + 1]);
}
};
复杂度分析:
- 时间复杂度:O(n),最坏情况下,遍历所有节点
- 空间复杂度:O(n),维护了一个队列,最坏情况下,可能装满树的所有节点