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

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

算法刷题2年前 (2023)更新 江南白衣
364 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、从上往下,找到一个节点时,标记这个节点的深度。查看该节点是否为叶子节点,如果是直接返回深度(找到第一个叶子节点即可,后面就不需要判断了)。
2、如果不是叶子节点,将其子节点标记深度(在父节点深度的基础上加1),再判断该节点是否为叶子节点。
3、使用链表实现一个先进先出的队列
4、循环终止条件:队列Queue为空
步骤:
1、二叉树TreeNode新增一个字段deep,用于记录节点的深度。
2、使用链表实现一个先进先出的队列 Queue<TreeNode> queue = new LinkedList<>();
3、记录根节点的深度为1,并将根节点加入队列。
4、当队列不为空时循环,取出队列中元素。
1)如果元素left和right都为null,则循环结束,返回当前node.deep;
2)如果元素有left,将left的深度+1,node.left.deep = node.deep + 1;
3)如果元素有right,同理。
时间复杂度:O(N)
空间复杂度:O(N)

package od1;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的最小深度(广度优先)
 * 给定一个二叉树,找出其最小深度,求最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * 原文地址:https://www.codernav.com/2845.html
 * 更多算法详解:https://www.codernav.com
 */
public class OdTest32 {
    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;
        }
        // 使用链表实现一个先进先出的队列
        Queue<TreeNode> queue = new LinkedList<>();
        // TreeNode无法记录深度,需要新增字段deep
        root.deep = 1;
        // 向队列添加元素,offer()与add()区别是前者当队列满了时不会抛异常,而是返回false
        queue.offer(root);
        // 队列为空跳出循环
        while (!queue.isEmpty()) {
            // 从队列中取出元素
            TreeNode node = queue.poll();
            // 左右节点都为空,则为叶子结点,循环结束
            if (node.left == null && node.right == null) {
                return node.deep;
            }
            // 不为空,则加入队列
            if (node.left != null) {
                node.left.deep = node.deep + 1;
                queue.offer(node.left);
            }
            if (node.right != null) {
                node.right.deep = node.deep + 1;
                queue.offer(node.right);
            }

        }

        return 0;

    }
}

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;
    }
}

两种算法的区别:深度优先与广度优先的区别是深度优先把叶子节点的深度标记为1,广度优先把根节点的深度标记为1。深度优先从下往上遍历,广度优先从上往下遍历。

© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...