问题描述：

Share

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 2hnodes inclusive at the last level h.

Example:

Input: 1 / \ 2 3 / \ / 4 5 6 Output: 6

源码：

最简单的肯定就是递归，但是这样完全没有用到完全二叉树的特性，肯定不是最佳的。

class Solution { public: int countNodes(TreeNode* root) { if (!root) return 0; return countNodes(root->left) + countNodes(root->right) + 1; } };

翻了一下别人的博客，有一种优化方案，其实我感觉也不优化，完全是为了用上而用上条件。就是如果一棵子树的最左边的长度等于右边的长度，就直接返回2^l-1，这样省去了遍历的步骤，但是这完全是一种“豪赌”，如果不满足条件，损耗会更大。

class Solution { public: int countNodes(TreeNode* root) { if ( !root ) return 0; int hl = 1; TreeNode* l = root->left; int hr = 1; TreeNode* r = root->right; while ( l ){ ++hl; l = l->left; } while ( r ){ ++hr; r = r->right; } if ( hr==hl ) return pow(2, hr)-1; return Solution::countNodes(root->left) + Solution::countNodes(root->right) + 1; } };

还有一种类似于二分查找的算法，很牛皮，首先我们需要一个depth函数用来计算最大高度，若当前结点不存在，则返回 -1。我们对当前结点调用 depth函数，若为 -1，则说明当前结点不存在，直接返回0。否则就对右子结点调用depth 函数，若返回值为 d-1，说明左子树是一棵完美二叉树，再加上当前结点，总共是 2^hd个，即 1<<d，若对右子结点调用 depth 函数的返回值不为 d-1，说明右子树一定是完美树，加上当前结点为 2^(d-1)，即 1<<(d-1)

class Solution { public: int depth(TreeNode* root){ return root ? (1+depth(root->left)) : -1; } int countNodes(TreeNode* root) { int d = depth(root); if(d == -1) return 0; cout<<d<<endl; if (depth(root->right) == d-1) return countNodes(root->right) + (1<<d); return (1<<(d-1)) + countNodes(root->left); } };