222. Count Complete Tree Nodes
Đề Bài
Given the root of a complete binary tree, return the number of the nodes in the tree.
According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, 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.
Design an algorithm that runs in less than O(n) time complexity.
Example 1:
Input: root = [1,2,3,4,5,6] Output: 6
Example 2:
Input: root = [] Output: 0
Example 3:
Input: root = [1] Output: 1
Constraints:
- The number of nodes in the tree is in the range
[0, 5 * 104]. 0 <= Node.val <= 5 * 104- The tree is guaranteed to be complete.
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n²)
💾 Không gian
O(1)
Lời Giải
C++
0222-count-complete-tree-nodes.cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
int cnt;
public:
void LNR(TreeNode *root) {
if (!root) {
return;
}
LNR(root->left);
cnt++;
LNR(root->right);
}
int countNodes(TreeNode* root) {
cnt = 0;
LNR(root);
return cnt;
}
};
Python
0222-count-complete-tree-nodes.py
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
dq = deque([root])
cnt = 0
while dq:
n = len(dq)
cnt += n
for _ in range(n):
node = dq.popleft()
if node.left:
dq.append(node.left)
if node.right:
dq.append(node.right)
return cnt