一、二叉树最大深度

二叉树的最大深度是根节点到叶子节点的最大长度

1.1 最大深度的递归实现

传入根节点，得到左右子树的高度，取较大值。然后不停的递归即可。这里需要注意的是如果不是空结点返回的是深度+1.
就比如一颗二叉树
 1
2  3
传入根节点1，不为空
传入左孩子结点（左孩子结点的左右孩子均为空，则返回0）
传入右孩子结点（右孩子结点的左右孩子均为空，则返回0）
最终返回0
显然是不对的。因为子树的根节点即使没有左右孩子，高度也应该为1
下面是实现代码:

  public static int maxDeepRecrusion(BTNode node) {
        if (node == null) {
            return 0;
        }
        int leftDeep = maxDeepRecrusion(node.leftChild);
        int rightDeep = maxDeepRecrusion(node.rightChild);
        //加1是因为要把每个字数的根节点也算进去
        return leftDeep > rightDeep ? (leftDeep + 1) : (rightDeep + 1);
    }

1.2 最大深度的非递归实现

前面我们介绍的最大宽度利用的是层次遍历的思路，得到了每一层的结点数量，在此基础上我们只需要每层+1即可得到最大深度

public static int maxDeep(BTNode node) {
        //如果为空
        if(node == null){
            return 0;
        }
        int maxDeep = 0, width;
        ArrayDeque<BTNode> queue = new ArrayDeque<>();
        //根节点入队
        queue.add(node);
        while (!queue.isEmpty()) {
            width = queue.size();
            //每遍历一层深度+1
            maxDeep += 1;
            //注意这里循环的次数是width,出队的仅仅是每一层的元素
            for (int i = 0; i < width; i++) {
                BTNode nodeTemp = queue.poll();
                if (nodeTemp.leftChild != null) {
                    queue.add(nodeTemp.leftChild);
                }
                if(nodeTemp.rightChild != null) {
                    queue.add(nodeTemp.rightChild);
                }
            }
        }
        return maxDeep;
    }

---

二、二叉树的最小深度

二叉树的最小深度即为是根节点到叶子节点的最小长度

2.1 最小深度的递归实现

1. 如果根节点为空，则最小深度为0
2. 如果只有一个根节点(根节点的左右子树为空)，则最小深度为1
3. 如果左子树为空，右子树不为空，最小深度为1+右子树的最小深度
4. 如果右子树为空，左子树不为空，最小深度为1+左子树的最小深度
5. 如果左右子树都不为空，则最小深度为1+左右子树最小深度中的较小值
   我们由此可得代码：

public static int minDeepRecrusion(BTNode node) {
        if(node == null) {
            return 0;
        }
        if (node.leftChild == null) return minDeepRecrusion(node.rightChild) + 1;
        if (node.rightChild == null) return minDeepRecrusion(node.leftChild) + 1;
        return Math.min(minDeepRecrusion(node.leftChild),minDeepRecrusion(node.rightChild))+1;
    }

其实之前的递归代码也可以省去变量，用这种Math.min()的方式。
当我们使用递归的方式求最小深度的时候要考虑到一种情况，如果根节点左孩子一个结点，右孩子深度为1000，那么递归方法仍然会去遍历1000次，所以从效率上来讲是很浪费资源的，下面介绍的非递归实现方式就不会出现这个问题

2.2 最小深度的非递归实现

非递归最小深度也是在层次遍历的基础上，上一步我们已经得到了最大深度的层次遍历，我们只需要在此基础上加上条件，当出现叶子结点的时候结束遍历，返回当前深度即可。

public static int minDeep(BTNode node) {
        //如果为空
        if(node == null){
            return 0;
        }
        int minDeep = 0, width;
        ArrayDeque<BTNode> queue = new ArrayDeque<>();
        //根节点入队
        queue.add(node);
        while (!queue.isEmpty()) {
            width = queue.size();
            //若每一层的宽度大于maxWidth，则重新赋值
            minDeep += 1;
            //注意这里循环的次数是width,出队的仅仅是每一层的元素
            for (int i = 0; i < width; i++) {
                BTNode nodeTemp = queue.poll();
                //左右均为空表明是叶子结点
                if(nodeTemp.rightChild == null && nodeTemp.leftChild == null){
                    return minDeep;
                }
                if (nodeTemp.leftChild != null) {
                    queue.add(nodeTemp.leftChild);
                }
                if(nodeTemp.rightChild != null) {
                    queue.add(nodeTemp.rightChild);
                }
            }
        }
        return minDeep;
    }

---

三、测试代码

  /**
     * 构建二叉树
     *          3
     *       2     4
     *    5   2   2  4
     * 5
     * @param args
     */
    public static void main(String[] args) {
        int[] a = {3, 2, 4, 5, 2, 2, 4, 5};
        //利用数组创建完全二叉树
        BTNode root = BTNodeUtil.createBTNodebyArray(a);
        System.out.println("二叉树的层次遍历为：");
        level(root);
        System.out.println();
        System.out.println("该二叉树的递归最大深度为：" + maxDeepRecrusion(root));
        System.out.println("该二叉树的非递归最大深度为：" + maxDeep(root));
        System.out.println("该二叉树的递归最小深度为：" + minDeepRecrusion(root));
        System.out.println("该二叉树的递归最小深度为：" + minDeep(root));
    }

输出为

二叉树的层次遍历为：
3 2 4 5 2 2 4 5 
该二叉树的递归最大深度为：4
该二叉树的非递归最大深度为：4
该二叉树的递归最小深度为：3
该二叉树的递归最小深度为：3