【leetcode】111二叉树的最小深度

灰太狼 2021-10-03 02:14 375阅读 0赞

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

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

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

示例:

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

  1. 3

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

解题思路：在左右结点都为空的时候进行最小值的更新（基于层序遍历）

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public int minDepth(TreeNode root) {
  12.         int minD = Integer.MAX_VALUE;
  13.         if(root == null)
  14.             return 0;
  15.         Queue<TreeNode> queue = new LinkedList<>();
  16.         queue.add(root);
  17.         int ceng = 0;
  18.         while(!queue.isEmpty()){
  19.             int size = queue.size();
  20.             ceng++;
  21.             while(size>0){
  22.                 TreeNode cur = queue.poll();
  23.                 if(cur.left == null && cur.right == null){
  24.                     if(minD>ceng)
  25.                         minD = ceng;
  26.                 }else{
  27.                 if(cur.left != null)
  28.                     queue.offer(cur.left);
  29.                 if(cur.right != null)
  30.                     queue.offer(cur.right);
  31.                 }
  32.                     size --;     
  33.             }
  34.         }
  35.         return minD;    
  36.     }
  37. }

发表评论

表情：
评论列表 （有 0 条评论，375人围观）

还没有评论，来说两句吧...

相关阅读