求二叉树的最小深度（深度优先和广度优先）-Toy模板网

这篇具有很好参考价值的文章主要介绍了求二叉树的最小深度（深度优先和广度优先）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

自己建一个二叉树，然后分别使用深度优先和广度优先找到二叉树的最小深度。
代码中有注释哦~文章来源地址https://www.toymoban.com/news/detail-657136.html

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

/**
 * @author: Arbicoral
 * @Description: 求一个二叉树的最小深度
 *
 * 深度优先：从叶子节点开始，将叶子节点标为 1，开始向上递归
 * 广度优先：从根节点开始，将根节点深度设置为1，开始向下入队列
 */
public class BinaryTreeMinDepth {
    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(minDepth(node1));
        System.out.println(minDepth2(node1));
    }

    /**
     * 广度优先：从根节点开始
     */
    private static int minDepth2(TreeNode root) {
        if (root == null) return 0;
        // 用一个队列进行维护
        Queue<TreeNode> queue = new LinkedList<>();
        root.deep = 1;//设置根节点的深度为1
        // 当队列满的时候
        // 调用 add()会抛出一个unchecked 异常；
        // 调用 offer()会返回一个false
        queue.offer(root);//把 根节点入队列
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();// 从队列中取出一个元素
            // 判断是否为 叶子节点,是的话可以直接 return
            if (node.left==null && node.right==null){
                return node.deep;
            }
            // 如果不是的话，分别判断左子节点和右子节点
            if (node.left != null){
                node.left.deep = node.deep+1;//左子节点的深度为当前节点的深度+1
                queue.offer(node.left);//左子节点入队列
            }
            if (node.right != null){
                node.right.deep = node.deep+1;//右子节点的深度为当前节点的深度+1
                queue.offer(node.right);//右子节点入队列
            }
        }
        return 0;
    }


    /**
     * 深度优先：从叶子节点开始
     */
    private static int minDepth(TreeNode root) {
        if (root == null) return 0;
        // 寻找叶子节点
        if (root.left == null && root.right == null){
            return 1;
        }
        int min = Integer.MAX_VALUE;// 保存每一个节点的最小
        if (root.left != null){
            min = Math.min(minDepth(root.left), min);//递归
        }

        if (root.right != null){
            min = Math.min(minDepth(root.right), min);//递归
        }
        return min + 1;//加上根节点
    }

    static class TreeNode{
        private int val;
        private TreeNode left;
        private TreeNode right;
        int deep;// 表示该节点的深度

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