二叉树的最小深度

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

热度指数：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，点此查看相关信息

算法知识视频讲解

Java

牛客148901号

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int run (TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = run(root.left);
        int right = run(root.right);
        int height = 0;
        if (left != 0 && right != 0) {
            height = Math.min(left, right);
        } else if (left != 0) {
            height = left;
        } else {
            height = right;
        }
        return 1 + height;
    }
}

发表于 2024-05-13 21:23:11 回复(0)

Java

Isolated_Island

import java.util.*;

public class Solution {
    public int run (TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int depth = root.left == null ? Integer.MAX_VALUE : this.run(root.left);
        if (root.right != null) {
            depth = Math.min(depth, this.run(root.right));
        }
        return depth + 1;
    }
}

发表于 2022-05-17 17:05:16 回复(0)

Java

pein531

深度优先搜索，到达叶子节点时就更新一次最小深度，否则继续向下搜索。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int minDepth = Integer.MAX_VALUE;
    public int run (TreeNode root) {
        // write code here
        if(root == null) return 0;
        dfs(root, 1);
        return minDepth;
    }
    
    private void dfs(TreeNode root, int depth) {
        if(root == null) return;
        if(root.left == null && root.right == null){
            // 到了叶子节点，更新最小深度
            minDepth = Math.min(depth, minDepth);
        }else{
            dfs(root.left, depth + 1);
            dfs(root.right, depth + 1);
        }
    }
}

发表于 2021-12-15 10:02:31 回复(0)