111. 二叉树的最小深度

[swiftwind0405]

方法一：广度优先遍历

解题思想：
在广度优先遍历过程中，如果遇到叶子节点，停止遍历，返回节点层级。

• 广度优先遍历整棵树，并记录每个节点的层级
• 遇到叶子节点，返回节点层级，停止遍历
  代码：

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)，维护了一个队列，最坏情况下，可能装满树的所有节点