完全二叉树计数

给定一棵完全二叉树的根节点root，返回这棵树的节点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。

给定树的根结点root，请返回树的大小。

思路：深度为h的二叉树至多有2^h-1个结点（h>=1）。换句话说，满二叉树中前k层的结点个数为2^h-1。

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class CountNodes { public: int count(TreeNode* root) { int res=0; countTree(root,res); return res; } void countTree(TreeNode* root,int &res){ int lh=0,rh=0; if(root==NULL) return; res++; if(root->left==NULL&&root->right==NULL) return; TreeNode *lroot=root->left; TreeNode *rroot=root->right; while(lroot){ //从左子树头节点开始，走到最后一个节点 lh++; //左子树的深度 lroot=lroot->left; } while(rroot){ //从右子树头节点开始，走到最后一个节点 rh++; //右子树的深度 rroot=rroot->left; } if(lh==rh){ //遍历到最后,如果lh==rh，说明左右子树深度相等 res+=pow(2,lh)-1; //pow(x,y)求x的y次方 左子树是满二叉树，求其结点个数 countTree(root->right,res); }else{ res+=pow(2,rh)-1; //子树是满二叉树，求其结点个数 countTree(root->left,res); } } };