222. 完全二叉树的节点个数

1、概要

给出一个完全二叉树，求出该树的节点个数。

示例 1：

• 输入：root = [1,2,3,4,5,6]
• 输出：6

首先按照普通二叉树的逻辑来求。这道题目的递归法（后序）和求二叉树的深度(取MAX)写法类似， 而迭代法，遍历模板稍稍修改一下，记录遍历的节点数量就可以了

2、思路

普通二叉树

递归法

• 递归函数参数与返回值

 private int reCurSion(TreeNode root)

• 终止条件

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

• 单层逻辑（累加）

return reCurSion(root.left)+reCurSion(root.right) + 1;

迭代法

加一个变量result，统计节点数量就可以了

在每层的for 增设result++，while循环退出后返回即可

完全二叉树性质

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

• 情况一：可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。

  满二叉树（Full Binary Tree）是一种特殊的二叉树，其中每个节点要么是叶节点（没有子节点），要么有两个子节点。给定满二叉树的高度为h，其节点数量可以用以下公式计算：

  节点数量 = 2^(h+1) - 1

  这个公式可以这样理解：

  1. 在高度为0时（只有一个根节点），节点数量为1，符合公式2^(0+1) - 1 = 1。
  2. 每增加一层高度，节点数量翻倍。例如，高度为1时，节点数量为2；高度为2时，节点数量为4；高度为3时，节点数量为8，以此类推。
  3. 由于满二叉树的特性，每一层的节点数量都是最大可能的，因此总节点数量等于每一层节点数量的总和。通过等比数列求和公式，我们可以得到上述的节点数量公式。

  请注意，这个公式仅适用于满二叉树。对于非满二叉树（如完全二叉树、平衡二叉树等），节点数量的计算方式会有所不同。

• 情况二：分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。

如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。

在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。不等于则不是满

3、代码

class Solution {
    public int countNodes(TreeNode root) {
        //return reCurSion(root);
        //return iTeRation(root);
        return comPleteBinaryTree(root);
    }

    private int reCurSion(TreeNode root){
        if(root == null){return 0;}

        return reCurSion(root.left)+reCurSion(root.right) + 1;
    }

    private int iTeRation(TreeNode root){
        if(root == null){return 0;}
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int res = 0;
        while(!que.isEmpty()){
            int deep = que.size();
            for(int i = 0;i<deep;i++){
                TreeNode cur = que.poll();
                res++;
                if(cur.left!=null){que.offer(cur.left);}
                if(cur.right!=null){que.offer(cur.right);}
            }
        }
        return res;
    }

    private int comPleteBinaryTree(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++;
        }
        //完全二叉树，一定会有左孩子或者右孩子，为满二叉树，可以用公式 2^树深度-1计算
        //左深度等于右深度 ，则说明是满二叉树
        if(leftDepth == rightDepth){
             return (int)Math.pow(2,leftDepth+1) -1;
        //Math.pow 是 Java 中用于计算一个数的指数的函数。它接受两个参数：基数和指数，并返回基数的指数次方的结果。
        //需要注意的是，Math.pow 返回的结果是一个 double 类型，即使输入的参数是整数类型，返回的结果也将是 double 类型。如果需要得到整数类型的结果，可以使用强制类型转换来将其转换为整数类型。 
            
        }
        return comPleteBinaryTree(root.left) + 
            
            comPleteBinaryTree(root.right) +1;
    }
}