给出一个完全二叉树,求出该树的节点个数。
说明: 完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
示例:
输入:
1
/ \
2 3
/ \ /
4 5 6
输出: 6
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/count-complete-tree-nodes 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
int count = 0;
public:
int countNodes(TreeNode* root) {
if(root == NULL)
return 0;
count++;
countNodes(root->left);
countNodes(root->right);
return count;
}
};
class Solution {
int h, hL, hR;
public:
int countNodes(TreeNode* root) {
if(root == NULL)
return 0;
hL = leftHeight(root);
hR = rightHeight(root);
if(hL == hR)
return (1<<hL)-1;//或者 pow(2,hL)-1;
else//hL > hR
return 1+countNodes(root->left)+countNodes(root->right);
}
int leftHeight(TreeNode* root)
{
for(h = 0 ; root; root=root->left)
++h;
return h;
}
int rightHeight(TreeNode* root)
{
for(h = 0 ; root; root=root->right)
++h;
return h;
}
};
class Solution {
int h, hL, hR;
public:
int countNodes(TreeNode* root) {
if(root == NULL)
return 0;
hL = Height(root->left);
hR = Height(root->right);
if(hL == hR)
return (1<<hL)+countNodes(root->right);
else//hL > hR
return (1<<hR)+countNodes(root->left);
}
int Height(TreeNode* root)
{
for(h = 0 ; root; root=root->left)
++h;
return h;
}
};