题目描述
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例
提交的代码
你被骗了，我没写出来最优解。我自己的解题时复是O(n)，题目的进阶写法是设计出来一个时复小于n的，我没想出来。
学习到的方法
这里用到carl大佬的配图，自己懒得画了，我学到的这个方法也来自于人家的解答。链接：解答链接
图示：
完全二叉树的特性这里就不多说了，估计都知道，满二叉树的节点个数为2^h-1。这里的方法就是让左右两个指针分别向左和右下去，直到它们的left(右指针为right)为空，也就是分别统计左右子树的高度（因为是完全二叉树，可以这么求高度的），如果左右高度相同，那就用满二叉树的特性就可以求出当前树的节点个数；如果左右高度不同，那就递归下去。
class Solution {
public int countNodes(TreeNode root) {
if(root==null){
return 0;
}
TreeNode left=root.left;
TreeNode right=root.right;
int lenLeft=0;
int lenRight=0;
int curHeight=0;
while(left!=null){
lenLeft++;
left=left.left;
}
while(right!=null){
lenRight++;
right=right.right;
}
if(lenLeft==lenRight){
return (2<<lenLeft)-1;
}
return countNodes(root.left)+countNodes(root.right)+1;
}
}