二叉树的属性 - leetcode-222：完全二叉树的节点个数 - 《算法珠玑》

问题
解法一：递归
解法二：迭代
解法三：二分法+位运算（官解）

问题

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

示例 1：
leetcode-222：完全二叉树的节点个数 - 图1
输入：root = [1,2,3,4,5,6]
输出：6

示例 2：
输入：root = []
输出：0

示例 3：
输入：root = [1]
输出：1

解法一：递归

递归遍历的顺序为后序遍历（左右中）

确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型。代码如下：
```
int getNodesNum(TreeNode cur)
```
确定终止条件：如果为空节点的话，就返回0，表示节点数为0

if (cur == NULL) return 0;

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

int leftNum = getNodesNum(cur.left);      // 左
int rightNum = getNodesNum(cur.right);    // 右
int treeNum = leftNum + rightNum + 1;      // 中
return treeNum;

class Solution {
  public int countNodes(TreeNode root) {
      if(root == null){
          return 0;
      }
      int leftNum = countNodes(root.left);
      int rightNum = countNodes(root.right);
      return leftNum + rightNum + 1;
  }
}

解法二：迭代

//超时。。。。。。
class Solution{
    public int countNodes(TreeNode root){
        if(root == null){
            return 0;
        }
        int res = 0;
        Deque<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                res++;
                if(node.left != null){
                    queue.offer(root.left);
                }
                if(node.right != null){
                    queue.offer(root.right);
                }
            }
        }
        return res;
    }
}

解法三：二分法+位运算（官解）

左移运算符（<<）：每左移一位，相当于该数乘2 右移运算符（>>）：每右移一位，相当于该数除2

对于任意二叉树，都可以通过广度优先搜索或深度优先搜索计算节点个数，时间复杂度和空间复杂度都是 leetcode-222：完全二叉树的节点个数 - 图2 ，其中 n 是二叉树的节点个数。这道题规定了给出的是完全二叉树，因此可以利用完全二叉树的特性计算节点个数

规定根节点位于第 0 层，完全二叉树的最大层数为 h。根据完全二叉树的特性可知，完全二叉树的最左边的节点一定位于最底层，因此从根节点出发，每次访问左子节点，直到遇到叶子节点，该叶子节点即为完全二叉树的最左边的节点，经过的路径长度即为最大层数 h

当 0 ≤ i < h 时，第 i 层包含 2^i个节点，最底层包含的节点数最少为1，最多为 2^h
当最底层包含 1 个节点时，完全二叉树的节点个数是
当最底层包含 2^h个节点时，完全二叉树的节点个数是

因此对于最大层数为 h 的完全二叉树，节点个数一定在 leetcode-222：完全二叉树的节点个数 - 图4 的范围内，可以在该范围内通过二分查找的方式得到完全二叉树的节点个数

具体做法是，根据节点个数范围的上下界得到当前需要判断的节点个数 k，如果第 k 个节点存在，则节点个数一定大于或等于 k，如果第 k 个节点不存在，则节点个数一定小于 k，由此可以将查找的范围缩小一半，直到得到节点个数。

如何判断第 k 个节点是否存在呢？如果第 k 个节点位于第 h 层，则 k 的二进制表示包含 h+1 位，其中最高位是 1，其余各位从高到低表示从根节点到第 k 个节点的路径，0 表示移动到左子节点，1 表示移动到右子节点。通过位运算得到第 k 个节点对应的路径，判断该路径对应的节点是否存在，即可判断第 k 个节点是否存在 leetcode-222：完全二叉树的节点个数 - 图5

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int level = 0;
        TreeNode node = root;
        while (node.left != null) {
            level++;
            node = node.left;
        }
        int low = 1 << level, high = (1 << (level + 1)) - 1; //1 << level：1向左移level位
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (exists(root, level, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }
    public boolean exists(TreeNode root, int level, int k) {
        int bits = 1 << (level - 1);
        TreeNode node = root;
        while (node != null && bits > 0) {
            if ((bits & k) == 0) {
                node = node.left;
            } else {
                node = node.right;
            }
            bits >>= 1;
        }
        return node != null;
    }
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/count-complete-tree-nodes/solution/wan-quan-er-cha-shu-de-jie-dian-ge-shu-by-leetco-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。