Given a complete binary tree, count the number of nodes.
Note:
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Example:
Input:
1
/ 2 3
/ \ /
4 5 6
Output: 6
题目大意：
计算完全二叉树树的节点数
解法：
采用中序遍历树的方法，遍历到一个节点，节点数目增加。但是这种做法并没有使用到完全二叉树树的特性。
Java：
class Solution {
int count=0;
public int countNodes(TreeNode root) {
if(root==null) return 0;
countNodes(root.left);
count++;
countNodes(root.right);
return count;
}
}
不停的向左走可以找到树的高度，单个节点树的高度为0，如果整个树为空，那么树的高度是-1。
每次只需要检查右子树树高是不是h-1，如果是，说明左子树是一个完全二叉树，节点数是2^h+右子树节点数
如果不是，说明右子树是一个完全二叉树，节点数是2^(h-1)+左子树节点数
class Solution {
private int height(TreeNode root){
if(root==null) return -1;
return 1+height(root.left);
}
public int countNodes(TreeNode root) {
int nodes=0;
int h=height(root);
while(root!=null){
if(height(root.right)==h-1){
nodes+=1<<h;
root=root.right;
}else{
nodes+=1<<h-1;
root=root.left;
}
h--;
}
return nodes;
}
}
leetcode[222] Count Complete Tree Nodes
原文：https://www.cnblogs.com/xiaobaituyun/p/10811257.html