当前位置：首页 > ds >正文

leetcode111. 二叉树的最小深度

ds 2025/9/5 4:37:18

问题描述：

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回它的最小深度 2.

思路：见代码

上代码，拿去即可运行：

package onlyqi.daydayupgo06.leetcode;public class TreeNode {private Integer value;private TreeNode left;private TreeNode right;public TreeNode() {}public TreeNode(Integer value) {this.value=value;}public TreeNode(Integer value, TreeNode left, TreeNode right) {this.value = value;this.left = left;this.right = right;}public Integer getValue() {return value;}public void setValue(Integer value) {this.value = value;}public TreeNode getLeft() {return left;}public void setLeft(TreeNode left) {this.left = left;}public TreeNode getRight() {return right;}public void setRight(TreeNode right) {this.right = right;}
}

    public static void main(String[] args) {TreeNode treeNode1 = new TreeNode(1);TreeNode treeNode2 = new TreeNode(2);TreeNode treeNode3 = new TreeNode(3);TreeNode treeNode4 = new TreeNode(4);TreeNode treeNode5 = new TreeNode(5);TreeNode treeNode6 = new TreeNode(6);TreeNode treeNode7 = new TreeNode(7);treeNode2.setLeft(treeNode4);treeNode2.setRight(treeNode5);treeNode1.setLeft(treeNode2);treeNode1.setRight(treeNode3);treeNode5.setLeft(treeNode6);
//        treeNode3.setLeft(treeNode7);System.out.println(getHeightBFS1(treeNode1));public static int getHeightBFS1(TreeNode root) {if (root == null) return 0;int height = 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int levelSize = queue.size();height++;for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll();if (node.getLeft() == null && node.getRight() == null) {return height;}if (node.getLeft() != null) queue.offer(node.getLeft());if (node.getRight() != null) queue.offer(node.getRight());}}return height;}
}

运行结果：