leetcode111.二叉树的最小深度

leetcode111.二叉树的最小深度

三月 14, 2020

leetcode111.二叉树的最小深度

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。

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

  3
 / \
9  20
  /  \
 15   7

返回它的最小深度 2.

方法很多，我第一个想到的额是层序遍历，bfs。当某个节点左右儿子都是空，说明这就是最短的那个了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int minDepth(TreeNode root) {
            if(root==null)return 0;
        int depth=0;
        Queue<TreeNode>queue=new LinkedList<>();
        queue.add(root);
        int count=1;
        int flag=0;
        while(!queue.isEmpty()){
            count=queue.size();
            depth++;
            for(int i=0;i<count;i++){
                TreeNode node=queue.poll();
                if(node.left==null&&node.right==null){
                    
                    flag=1;
                    break;
                }
                if(node.left!=null)queue.add(node.left);
                if(node.right!=null)queue.add(node.right);
            }
            if(flag==1)break;
        }
        return depth;
    }

leetcode 36/100