LeetCode 222：完全二叉树的节点个数
题目： 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
思路： 如果不用完全二叉树的性质，此题用递归和BFS都能做，比较简单
方法一：递归 or BFS
递归三步曲：
- 参数root，返回值不需要， num作为成员变量
- 终止条件，为null则return
- 单层逻辑：只需要num++即可
class Solution {
int num=0;
public int countNodes(TreeNode root) {
check(root);
return num;
}
void check(TreeNode root){
if(root==null){
return;
}
check(root.left);
check(root.right);
num++; // 后序遍历
}
}
时间复杂度 O(N)
层序遍历（BFS）：
class Solution {
int num=0;
public int countNodes(TreeNode root) {
Queue<TreeNode> nodes=new LinkedList<>();
if(root!=null){
nodes.add(root);
}
while(!nodes.isEmpty()){
TreeNode n=nodes.poll();
num++;
if(n.left!=null){
nodes.add(n.left);
}
if(n.right!=null){
nodes.add(n.right);
}
}
return num;
}
}
时间复杂度 O(N)：
方法二：完全二叉树的性质
如果是满二叉树，则节点个数和层数呈指数关系： 假设节点个数n，层数为h， 则 n=2^h-1
public int countNodes(TreeNode root) {
int h = 0;
// 计算树的高度
while (root != null) {
root = root.left;
h++;
}
// 节点总数就是 2^h - 1
return (int)Math.pow(2, h) - 1;
而完全二叉树比普通二叉树特殊，但又没有满二叉树那么特殊，计算它的节点总数，可以说是普通二叉树和满二叉树的结合版，
从根节点root开始，分别计算最左侧节点数hl和最右侧节点数hr， 若hr hl不等，则会进入递归，而每一轮都hi先判断hr和hl是否相等 由于完全二叉树的性质，其子树一定会有一棵是满二叉树，即有一个递归迟早会停下来！可以使用指数公式计算出节点个数而不再需要递归 而另一个递归的普通二叉树，当递归到叶子节点时，其左右节点均为null，可以有终止条件停止递归！ 如果不写终止条件也可以，叶子节点也可以视为一个左右子节点个数=0的特殊满二叉树，使用公式2^0-1=0 ，与直接 return 0 效果一样。
public int countNodes(TreeNode root) {
// 满二叉树+普通二叉树
if(root==null){
return 0; // 终止条件
}
// 左侧深度
TreeNode r=root,l=root; // 左右两指针
int hl=0,hr=0;
while(l!=null){
// 最左侧深度
l=l.left;
hl++;
}
// 右侧深度
while(r!=null){
// 最右侧深度
r=r.right;
hr++;
}
// 满二叉树 n=2^h-1
if(hr==hl){
return (int)Math.pow(2,hl)-1; // Math.pow() 返回double
}
// 普通二叉树
// 可视为后序遍历，只是先判断是否为满二叉树
return countNodes(root.right) + countNodes(root.left) + 1; // 加1指加上当前root节点
// 当左右节点数不等时，才会递归！ 若是满二叉树则直接公式计算；
}
}
时间复杂度：(logN*logN))
由于子树一定有一棵是满的，所以一定会触发 hl == hr，只消耗 O(logN) 的复杂度而不会继续递归。 所以算法的递归深度就是树的高度 O(logN)，每次递归所花费的时间就是 while 循环，需要O(logN)，所以总体的时间复杂度是 O(logN*logN)。
