111. 二叉树的最小深度

1、概要

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

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

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

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）

二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）

直觉上好像和求最大深度差不多，其实还是差不少的。本题依然是前序遍历和后序遍历都可以，前序求的是深度，后序求的是高度。

最小深度，注意两个，根节点，最近叶子节点，左右孩子都为空才是。

求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。

2、思路

递归法

递归函数和返回值

private int reCurSion(TreeNode node)

终止条件

遇到空节点返回0

if(node == null){return 0;}

单层逻辑

 int leftDepth = reCurSion(node.left);
        int rightDepth = reCurSion(node.right);
        if(node.left==null){// 当一个左子树为空，右不为空，这时并不是最低点
            return rightDepth+1;
        }
        if(node.right == null){// 当一个右子树为空，左不为空，这时并不是最低点
            return leftDepth+1;
        }

        return Math.min(leftDepth,rightDepth)+1;

迭代法

需要注意的是，只有当左右孩子都为空的时候，才说明遍历到最低点了。如果其中一个孩子不为空则不是最低点

 //如果当前节点的左右孩子都为空，直接返回最小深度
                if(cur.left ==null && cur.right == null){
                    return len;
                }

3、代码

class Solution {
    public int minDepth(TreeNode root) {
        //return order(root);
        return reCurSion(root);
    }

    private int reCurSion(TreeNode node){
        if(node == null){return 0;}
        int leftDepth = reCurSion(node.left);
        int rightDepth = reCurSion(node.right);
        if(node.left==null){
            return rightDepth+1;
        }
        if(node.right == null){
            return leftDepth+1;
        }

        return Math.min(leftDepth,rightDepth)+1;
    }
    
    public int order(TreeNode node){
        if(node == null){
            return 0;
        }
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);
        //可操作
        int len=0;

        while(!que.isEmpty()){
            
            int deep = que.size();
            //最小深度赋值
            len++;

            for(int i=0; i<deep; i++){
                TreeNode cur = que.poll();

                //如果当前节点的左右孩子都为空，直接返回最小深度
                if(cur.left ==null && cur.right == null){
                    return len;
                }
                
                if(cur.left!=null){
                    que.offer(cur.left);
                }
                if(cur.right!=null){
                    que.offer(cur.right);
                }
           
            }
            //可操作
        }
        return len;
    }

}