LeetCode 222: Count Complete Tree Nodes
Problem Description
Explanation
To solve this problem efficiently, we can use a binary search approach to find the last node in the complete binary tree. Once we find the last node, we can calculate the total number of nodes by counting the nodes in the left and right subtrees recursively. This approach leverages the properties of a complete binary tree to optimize the time complexity to O(log^2(n)).
- Find the height of the tree by traversing the left child nodes until we reach a null node.
- Perform a binary search on the last level of the tree to find the last node.
- Count the nodes in the left and right subtrees recursively.
- Calculate the total number of nodes as 2^(height)-1 + nodes in the left and right subtrees.
Time complexity: O(log^2(n)) Space complexity: O(log(n))
Solutions
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getLeftHeight(root);
int rightHeight = getRightHeight(root);
if (leftHeight == rightHeight) {
return (1 << leftHeight) - 1;
}
return 1 + countNodes(root.left) + countNodes(root.right);
}
private int getLeftHeight(TreeNode node) {
int height = 0;
while (node != null) {
height++;
node = node.left;
}
return height;
}
private int getRightHeight(TreeNode node) {
int height = 0;
while (node != null) {
height++;
node = node.right;
}
return height;
}
}Related LeetCode Problems
Loading editor...