LOADING

百度&必应权4, 日IP8000. 查看详情
自助收录

使用深度优先解决“二叉树的最小深度”问题

算法刷题2年前 (2023)更新 江南白衣
284 0 0
使用深度优先解决“二叉树的最小深度”问题

二叉树的最小深度
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5

使用深度优先解决“二叉树的最小深度”问题解法一:深度优先
遍历整棵树,找到每一个叶子节点,从叶子节点往上开始计算(使用递归),左右子节点都为空则记录深度为1;左右子节点只有一边,深度记录为子节点深度+1;左右两边都有子节点,则记录左右子节点的深度较小值+1。深度优先与广度优先的区别是深度优先把叶子节点的深度标记为1,广度优先把根节点的深度标记为1。深度优先从下往上遍历,广度优先从上往下遍历。
时间复杂度:O(N)
空间复杂度:O(logN) 取决于树的高度

package od1;

/**
 * 二叉树的最小深度(深度优先)
 * 给定一个二叉树,找出其最小深度,求最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * 原文地址:https://www.codernav.com/2843.html
 * 更多算法详解:https://www.codernav.com
 */
public class OdTest31 {
    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, node7, null);
        TreeNode node5 = new TreeNode(5, null, null);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, node6, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);
        // 递归 深度优先
        System.out.println(f(node1));
    }

    public static int f(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 1.判断是否为子节点,子节点的深度为1
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 最小深度 设置为一个最大值(重要)
        int min = Integer.MAX_VALUE;
        if (root.left != null) {
            min = Math.min(f(root.left), min);
        }
        if (root.right != null) {
            min = Math.min(f(root.right), min);
        }
        // 深度+1
        return min + 1;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    // 深度(广度优先维护深度新增字段)
    int deep;

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

 

© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...