222. 完全二叉树的节点个数
1. 思路
这个题最简单的做法就是暴力遍历，时间复杂度为O(n)。
我们现在用低于O(n)的做法解决问题。
对于一棵满二叉树，它的节点数 = 2 h - 1 (h 是指树一共有多少层)
- 头节点不断遍历左孩子直至为null，得到树高h。
- 遍历头节点右孩子的左边界，直到遍历到最左节点，如果最左节点所在的层数 = h，说明头节点root的左子树是满二叉树。那么左子树的节点数 = 2l - 1，l 是指左子树有多少层。那么root左子树节点数 + root节点数 = 2l - 1 + 1 = 2l 。接着递归遍历root的右子树，求右子树有多少节点，相加即可。
- 如果头节点右孩子的最左节点所在的层数 < h (绝不可能大于h，因为是完全二叉树)，说明头节点root的右子树是满二叉树。那么root的右子树的节点数 = 2l - 1，l 是指右子树有多少层。那么root右子树节点数 + root节点数 = 2l - 1 + 1 = 2l 。接着递归遍历root的左子树，求左子树有多少节点，相加即可。
有一个递归函数 int f(TreeNode node)，返回结果是以node为头节点的完全二叉树有多少个节点。
上图中树有四层高（h = 4），头节点a为第一层。
f(a)：
a的右子树的最左节点层数= 3 < 4，说明右子树是满二叉树。而右子树的树高2层。
计算公式：树的总高度h - a的层数 - 1 = 4 - 1 - 1 = 2 ，即右子树的节点数 = 2 2 - 1 = 3。右子树节点数 + a节点数 = 3 + 1 = 4 = 22 。之后递归调用a的左子树b。
f(a) = f(b) + 4
f(b):
b的右子树的最左节点层数 = 4，说明 b 的左子树是满二叉树。b 的 左子树树高2层。
计算公式：树的总高度h - b的层数 = 4 - 2 = 2，即b的左子树节点数 = 22 - 1 = 3。左子树节点数 + b节点数 = 3 + 1 = 4 = 22 。之后递归调用b的右子树c。
f(b) = f© + 4
f©:
c 的右子树为空，也就是右子树的最左节点 != 4，说明c的右子树是满二叉树。只不过是 0 个节点。
计算公式：**树的总高度h - c的层数 - 1 ** = 4 - 3 -1 = 0，即c的右子树节点数 = 20 - 1 = 0。在此基础上加上c节点数 = 0 + 1 = 1。之后递归调用c的左子树d。
f© = f(d) + 1
f(d):
d节点是叶节点，f(d) 直接返回1。
f(a) = f(b) + 4 = 10
f(b) = f© + 4 = 6
f© = f(d) + 1 = 2
f(d) = 1
2. 代码
public static int countNodes(TreeNode root) {if(root == null){return 0;}return f(root,1,mostLeft(root,1));}/**** @param cur - 当前节点* @param level - 当前节点所在层数* @param h - 整棵树的高度* @return 以cur为头节点的树的高度*/private static int f(TreeNode cur, int level, int h) {if (level == h){return 1;}/*** level 是 cur所在的层数* level + 1 才是 cur.right所在层数*/if (mostLeft(cur.right,level + 1) == h){/*** cur.right所在层数 = h* cur的左子树是满二叉树* 1 << (h - level) 意为 2向左移动1 << (h - level)为，即 2^(h - level)*/return (1 << (h - level)) + f(cur.right,level+1,h);}else {/**** cur的右子树是满二叉树*/return (1 << (h - level - 1)) + f(cur.left,level+1,h);}}/*** 求当前节点的最左节点所在的层数* @param cur - 当前节点* @param level - 当前节点的层数* @return 当前节点的最左节点所在的层数*/private static int mostLeft(TreeNode cur, int level) {while (cur != null){level++;cur = cur.left;}/*** 如果整棵树的根节点层数从0开始计数，那么返回level* 可根节点是从1开始计数，返回level-1，自己动笔算一下就明白了*/return level - 1; }
