day13二叉树的最大深度&二叉树的最小深度&完全二叉树的节点个数（递归三部曲详解）_二叉树的深度和节点数

        继续学习二叉树的知识，在解决这三个问题之前我们要先来理解下深度和高度的知识，这些是解决问题的基础。

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数
• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数

目录

1.力扣104（二叉树的最大深度）

2.力扣111（二叉树的最小深度）

3.力扣222（完全二叉树的节点数）

1）普通二叉树（递归三部曲）：

2）完全二叉树（递归三部曲）：

---

1.力扣104（二叉树的最大深度）

         本题利用递归三部曲来解决，在解决问题之前，我们要先确定遍历二叉树的方式，根节点的高度也就是最大深度，根据这个性质我们可以确定使用后续遍历的方式，因为后续遍历的顺序是左右中，我们在利用递归遍历完左子树和右子树后，把高度返回给中节点，中节点进行合并后返回给根节点，我们现在来确定三部曲的参数：

1. 确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。
2. 确定终止条件：如果为空节点的话，就返回0，表示高度为0。
3. 确定单层递归的逻辑：先求它的左子树的深度，再求的右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

                        

根据这三部我们可以写出代码：

    public int maxDepth(TreeNode root) {
        return getHeight(root);
    }
    int getHeight(TreeNode root){
        if(root==null){//确定终止条件
            return 0;
        }
        int left = getHeight(root.left); //左
        int right = getHeight(root.right); //右
        return Math.max(left,right)+1; //中
    }

2.力扣111（二叉树的最小深度）

        这个题和上个题目很相似可以说非常相似，只需要我们取最小值，但是做这个题目我们要想到一个容易被忽略的点，也就是根节点左子树为空的时候返回的是0，我们需要排除这个情况，所以在进行返回中节点的时候需要判断一下。

这里我放下需要思考的代码：

        if(root.left==null&&root.right!=null){
            return right+1;
        }
        if(root.left!=null&&root.right==null){
            return left+1;
        }

下面是整体代码：

    public int minDepth(TreeNode root) {
        return getHeight(root);
    }
    int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int left = getHeight(root.left); //左
        int right = getHeight(root.right); //右
        int mid = Math.min(left,right); //中
        //需要特殊处理的地方--》也就是左或者右节点为空的情况
        if(root.left==null&&root.right!=null){
            return right+1;
        }
        if(root.left!=null&&root.right==null){
            return left+1;
        }
        return mid+1;
    }

3.力扣222（完全二叉树的节点数）

        本题当成普通二叉树来解决，会比较容易想到，我先来说下普通二叉树递归方法解决，再来说下完全二叉树的递归遍历。而这题我们依旧利用后序遍历来解决

1）普通二叉树（递归三部曲）：

• 确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。

    int getNums(TreeNode root)

• 确定终止条件：如果为空节点的话，就返回0，表示节点数为0。

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

• 确定单层递归的逻辑：先求它的左子树的节点数量，再求的右子树的节点数量，最后取总和再加一 （加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。

        int left = getNums(root.left); //左
        int right = getNums(root.right); //右
        int mid = left+right+1; //中
        return mid;

最终代码：

    public int countNodes(TreeNode root) {
        return getNums(root);
    }
    int getNums(TreeNode root){
        if(root==null){
            return 0;
        }
        int left = getNums(root.left);
        int right = getNums(root.right);
        int mid = left+right+1;
        return mid;
    }

2）完全二叉树（递归三部曲）：

• 确定递归函数的参数和返回值：

    public int countNodes(TreeNode root) 

• 确定终止条件：我们遇到空节点的时候，也就是遍历至尾部的时候需要返回；但是我们需要利用完全二叉树的性质来解决本题，在二叉树中有这样的一个公式 2^树深度 - 1 来计算注意（根节点深度为1），当我们遇到满二叉树的时候可以直接利用这个公式来返回值，若不是满二叉树的话，我们需要继续递归向下数节点的数量，然后返回。（这里用到了位运算，感谢大佬的思路）

        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth=0,rightDepth=0;
        while(left!=null){
            left=left.left;
            leftDepth++;
        }
        while(right!=null){
            right=right.right;
            rightDepth++;
        }
        if(leftDepth==rightDepth){
            return (2<<leftDepth)-1;
        }

• 确定单层递归的逻辑：当不满足返回条件的时候，我们就需要利用递归向下遍历

        int leftNum=countNodes(root.left);
        int rightNum=countNodes(root.right);
        return leftNum+rightNum+1;

最终代码：

    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth=0,rightDepth=0;
        while(left!=null){
            left=left.left;
            leftDepth++;
        }
        while(right!=null){
            right=right.right;
            rightDepth++;
        }
        if(leftDepth==rightDepth){
            return (2<<leftDepth)-1;
        }
        int leftNum=countNodes(root.left);
        int rightNum=countNodes(root.right);
        return leftNum+rightNum+1;
    }