# 222. Count Complete Tree Nodes

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


A Complete Binary Tree （CBT) is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

A Perfect Binary Tree(PBT) is a tree with all leaf nodes at the same depth. All internal nodes have degree 2.

A Full Binary Tree (FBT) is a tree in which every node other than the leaves has two children.

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


class Solution {
public:
int countNodes(TreeNode* root) {
int hLeft = 0, hRight = 0;
TreeNode *pLeft = root, *pRight = root;
while (pLeft) {
++hLeft;
pLeft = pLeft->left;
}
while (pRight) {
++hRight;
pRight = pRight->right;
}
if (hLeft == hRight) return pow(2, hLeft) - 1;
return countNodes(root->left) + countNodes(root->right) + 1;
}
};


class Solution {
public:
int countNodes(TreeNode* root) {
int hLeft = leftHeight(root);
int hRight = rightHeight(root);
if (hLeft == hRight) return pow(2, hLeft) - 1;
return countNodes(root->left) + countNodes(root->right) + 1;
}
int leftHeight(TreeNode* root) {
if (!root) return 0;
return 1 + leftHeight(root->left);
}
int rightHeight(TreeNode* root) {
if (!root) return 0;
return 1 + rightHeight(root->right);
}
};


class Solution {
public:
int countNodes(TreeNode* root) {
int res = 0, h = getHeight(root);
if (h < 0) return 0;
if (getHeight(root->right) == h - 1) return (1 << h) + countNodes(root->right);
return (1 << (h - 1)) + countNodes(root->left);
}
int getHeight(TreeNode* node) {
return node ? (1 + getHeight(node->left)) : -1;
}
};


class Solution {
public:
int countNodes(TreeNode* root) {
int res = 0, h = getHeight(root);
if (h < 0) return 0;
while (root) {
if (getHeight(root->right) == h - 1) {
res += 1 << h;
root = root->right;
} else {
res += 1 << (h - 1);
root = root->left;
}
--h;
}
return res;
}
int getHeight(TreeNode* node) {
return node ? (1 + getHeight(node->left)) : -1;
}
};


Github 同步地址：

https://github.com/grandyang/leetcode/issues/222

Closest Binary Search Tree Value

https://leetcode.com/problems/count-complete-tree-nodes/

https://leetcode.com/problems/count-complete-tree-nodes/discuss/61958/Concise-Java-solutions-O(log(n)2)

https://leetcode.com/problems/count-complete-tree-nodes/discuss/61953/Easy-short-c%2B%2B-recursive-solution

https://leetcode.com/problems/count-complete-tree-nodes/discuss/61948/Accepted-Easy-Understand-Java-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation