222. Count Complete Tree Nodes

  • 27.1%

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.


方法一:

本题是求完全二叉树节点的个数。完全二叉树,就是如果深度为d,那么d-1层至0层都是满二叉树,d层从左向右排列。完全二叉树,就是d层是满的。

高度为h的完全二叉树,节点数为

1
2^h - 1

,如果完全二叉树是满二叉树,就只这个结果。如果不是,就递归,两个相加。

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* 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) {
if(!root) return 0;
int hl = 0, hr = 0;
TreeNode* left = root, * right = root;
while(left){
hl++;
left = left->left;
}
while(right){
hr++;
right = right->right;
}
if(hl == hr) return pow(2, hl)-1;
return 1 + countNodes(root->left) + countNodes(root->right);
}
};

https://discuss.leetcode.com/topic/15515/easy-short-c-recursive-solution

Easy short c++ recursive solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {

public:

int countNodes(TreeNode* root) {

if(!root) return 0;

int hl=0, hr=0;

TreeNode *l=root, *r=root;

while(l) {hl++;l=l->left;}

while(r) {hr++;r=r->right;}

if(hl==hr) return pow(2,hl)-1;

return 1+countNodes(root->left)+countNodes(root->right);

}

};

https://discuss.leetcode.com/topic/31457/a-very-clear-recursive-solution-isn-t-it

A very clear recursive solution, isn’t it?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* 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) {
if(!root) return 0;
int lh = height(root->left);
int rh = height(root->right);
if(lh == rh)
return (1 << lh) + countNodes(root->right); /*1(根节点) + (1<<lh)-1(完全左子树) + # of rightNode */
else
return (1 << rh) + countNodes(root->left); /*1(根节点) + (1<<rh)-1(完全右子树) + # of leftNode*/
}
private:
int height(TreeNode *root){ //get the height of a complete binary tree.
if(!root) return 0;
return 1 + height(root->left);
}
};

https://discuss.leetcode.com/topic/19215/simple-c-recursive-solution

Simple C++ recursive solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int getLeftHeight(TreeNode* root) {
int height = 0;
while(root) {
root = root->left;
height++;
}
return height;
}

int countNodes(TreeNode* root) {
if(!root) return 0;

int left_height = getLeftHeight(root->left);
int right_height = getLeftHeight(root->right);

if(left_height == right_height)
return pow(2, left_height) + countNodes(root->right);

return pow(2, right_height) + countNodes(root->left);
}

https://discuss.leetcode.com/topic/23830/68ms-c-solution-using-binary-search-with-brief-explanation

68ms C++ solution using binary search with brief explanation.

The thought is simple. We just consider the lowest level of the tree.

The left child and right child just divide the tree lower than the current node to 2 part.

So what this code do is first check the right most child of the current node’s left child.

If this child is exist, we know that there may be more nodes on the right side of the tree. So we move the current node to it’s right child. And repeat until we reach the lowest level.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int countNodes(TreeNode* root) {
if(!root) return 0;
TreeNode *temp = root;
int height = 0, count = 0, level;
while(temp) {
temp = temp->left;
height ++;
}
temp = root;
level = height - 2;
while(level >= 0) {
TreeNode *left = temp->left;
for(int i = 0;i < level;i ++) {
left = left->right;
}
if(left) {
temp = temp->right;
count += (1 << level);
} else temp = temp->left;
level --;
}
if(temp) count ++;
return (1 << (height - 1)) + count - 1;
}

https://discuss.leetcode.com/topic/17971/my-python-solution-in-o-lgn-lgn-time

My python solution in O(lgn * lgn) time

compare the depth between left sub tree and right sub tree.

A, If it is equal, it means the left sub tree is a full binary tree

B, It it is not , it means the right sub tree is a full binary tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
# @param {TreeNode} root
# @return {integer}
def countNodes(self, root):
if not root:
return 0
leftDepth = self.getDepth(root.left)
rightDepth = self.getDepth(root.right)
if leftDepth == rightDepth:
return pow(2, leftDepth) + self.countNodes(root.right)
else:
return pow(2, rightDepth) + self.countNodes(root.left)

def getDepth(self, root):
if not root:
return 0
return 1 + self.getDepth(root.left)
谢谢你,可爱的朋友。