二叉树的最小深度

[编程题]二叉树的最小深度

热度指数：3679 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一颗节点数为N的二叉树，求其最小深度。最小深度是指树的根节点到最近叶子节点的最短路径上节点的数量。

（注：叶子节点是指没有子节点的节点。）

数据范围：

0<=N<=6000

0<=val<=100

你能使用时间复杂度为O(N)，空间复杂度为O(logN)的解法通过本题吗？

例如当输入{1,2,3,4,5}时，对应的二叉树如下图所示：

可以看出离根节点最近的叶子节点是节点值为3的节点，所以对应的输出为2。

示例1

输入

{1,2,3,4,5}

输出

示例2

输入

{1,#,2,#,3}

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Javascript

nicole27

function run( root ) {
    // write code here
    let queue = [];
    let count = 0;
    if(root==null) return count;
    queue.push(root);
    while(queue.length>0){
        let len = queue.length;
        count++;
        while(len--){
            let node = queue.shift();
            if(node.left==null&&node.right==null) return count;
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
            
        }
    }
    return count;
}

发表于 2022-03-25 14:11:22 回复(0)