Given a complete binary tree, count the number of nodes.
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.
解题思路
全然遍历会超时。能够从根节点開始分别计算左子树和右子树的高度。假设相等，则为满二叉树，结点个数为2n−1。假设高度不相等，则结点个数为左子树结点个数+右子树结点个数+1。（高度n是包括根节点的高度）
实现代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int countNodes(TreeNode* root) {
int leftHight = getLeft(root);
int rightHeight = getRight(root);
if (leftHight == rightHeight)
{
return pow(
2, leftHight) -
1;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
private:
int getLeft(TreeNode *root)
{
int height =
0;
while (root)
{
height++;
root = root->left;
}
return height;
}
int getRight(TreeNode *root)
{
int height =
0;
while (root)
{
height++;
root = root->right;
}
return height;
}
};
转载于:https://www.cnblogs.com/bhlsheji/p/4561692.html
相关资源：数据结构—成绩单生成器
