题目地址(111. 二叉树的最小深度)

https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

题目描述

  1. 给定一个二叉树，找出其最小深度。
  3. 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
  5. 说明：叶子节点是指没有子节点的节点。
  9. 示例 1：
  11. 输入：root = [3,9,20,null,null,15,7]
  12. 输出：2
  15. 示例 2：
  17. 输入：root = [2,null,3,null,4,null,5,null,6]
  18. 输出：5
  23. 提示：
  25. 树中节点数的范围在 [0, 105] 内
  26. -1000 <= Node.val <= 1000

前置知识


公司

  • 暂无

思路

使用迭代法层序遍历 遍历到第一个左右两个子节点都为空的即为二叉树的最小深度

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         public int minDepth(TreeNode root) {
  19.             Queue<TreeNode> queue = new LinkedList<>();
  20.             int num = 0;
  21.             if (root == null) {
  22.                 return num;
  23.             }
  24.             queue.offer(root);
  25.             while (!queue.isEmpty()) {
  26.                 int size = queue.size();
  27.                 num++;
  28.                 while (size > 0) {
  29.                     TreeNode poll = queue.poll();
  30.                     //遍历到第一个左右两个子节点都为空的即为二叉树的最小深度
  31.                     if (poll.left == null && poll.right == null) {
  32.                         return num;
  33.                     }
  34.                     if (poll.left != null){
  35.                         queue.offer(poll.left);
  36.                     }
  37.                     if (poll.right != null){
  38.                         queue.offer(poll.right);
  39.                     }
  40.                     size--;
  41.                 }
  43.             }
  44.             return num;
  45.         }
  46.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：111. 二叉树的最小深度 - 图1#card=math&code=O%28n%29&id=smZI7)
  • 空间复杂度：111. 二叉树的最小深度 - 图2#card=math&code=O%28n%29&id=bJwev)