DataStructure_Algorithm_HandBook_PreForLeetCode

111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

Constraints:

• The number of nodes in the tree is in the range [0, 105].
• -1000 <= Node.val <= 1000

solutions

这道题如果从层序遍历 bfs 的角度考虑，基本上遍历到某个层的第一个叶子节点，那么这个时候的深度肯定是最小的深度。

class Solution {
    public int minDepth(TreeNode root) {
         Deque<TreeNode> q = new LinkedList();
         if(root!=null) q.offer(root);
         int min_depth=0;
         while(!q.isEmpty()){
            min_depth++;
            int size = q.size();
            for(int i=0; i<size; i++){
                TreeNode node = q.poll();
                if(node.left==null && node.right==null){
                    return min_depth;
                }
                if(node.left!=null) q.offer(node.left);
                if(node.right!=null) q.offer(node.right);
            }
         }
       return min_depth; 
       //有些语言这个地方必须要 return，但是实际上肯定是不可能到这个地方的，可以随意 ///return 一个值，因为空节点 return 0，所以也可以返回 0 
    }
}

还有一种方法就是用 dfs 也可以，基于最大深度的模版改一改就可以了

class Solution {
     int depth = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
           //注意判断root 为空的情况
           if (root ==null) return 0;
           dfs(root,1);
           return depth;
    }
    void dfs(TreeNode root, int cur_depth){
        if(root == null) return;
        if(root.left ==null && root.right==null){
            //第一个叶子节点就是深度最小的点
            depth = Math.min(depth,cur_depth);
            return;
        }
        dfs(root.left,cur_depth+1);
        dfs(root.right,cur_depth+1);
    }    
}