需求
给你一棵** 完全二叉树** 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2的h次方 个节点。
示例 1：
二叉树
输入：root = [1,2,3,4,5,6]
输出：6
示例2
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
思路
计算节点按照递归或者层序遍历都是可以算出来节点数。
但是这个题目明确了是完全二叉树，也就是使用完全二叉树特性来做。
完全二叉树
以上方法都是按照普通二叉树来做的，对于完全二叉树特性不了解的同学可以看这篇 关于二叉树，你该了解这些！，这篇详细介绍了各种二叉树的特性。
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
大家要自己看完全二叉树的定义，很多同学对完全二叉树其实不是真正的懂了。
我来举一个典型的例子如题：
image.png
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
完全二叉树（一）如图：
image.png
完全二叉树（二）如图：
image.png
可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。
这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？
在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。
**
* 222. 完全二叉树的节点个数
*/
public class CountNodes222 {
// 通用递归解法
public int countNodesTy(TreeNode root) {
if(root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
public int countNodes(TreeNode root) {
if (root == null) return 0;
int leftHight = 0;int rightHigh = 0;
TreeNode leftNode = root.left;
TreeNode rightNode = root.right;
// 满二叉树结束条件。满二叉树用公式计算
while (leftNode != null) {// 球左子树深度
leftHight++;
leftNode = leftNode.left;
}
while (rightNode != null) {// 求右子树
rightHigh++;
rightNode = rightNode.right;
}
if (leftHight == rightHigh) {
// 2的多少次方，满二叉树计算公式
return (2 << leftHight) - 1;
}// 以上为结束条件
// 执行主体
int leftCount = countNodes(root.left);// 左
int rightCount = countNodes(root.right);// 右
// 如果最后一层数据不满足满二叉树单独存在，其实是左右为0的满二叉树
return leftCount + rightCount+1;// 中
}
// 迭代法
public int countNodesDd(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int result = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size -- > 0) {
TreeNode cur = queue.poll();
result++;
if (cur.left != null) queue.offer(cur.left);
if (cur.right != null) queue.offer(cur.right);
}
}
return result;
}
}
验证结果
