Description
https://leetcode.com/problems/count-complete-tree-nodes/
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.
Explanation
The idea is that we can check if the depth of the leftmost path equals the depth of the rightmost path. If both paths have equal lengths, that means the tree is a full binary tree, the tree’s node count = 2^h – 1, where h is the height of the tree. If two paths have different lengths, the total count of the tree’s nodes = the count of the left tree nodes + the count of the right tree nodes + 1(root node).
Python Solution
# 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:
left_depth = self.find_left_depth(root)
right_depth = self.find_right_depth(root)
if left_depth == right_depth:
return 2**left_depth - 1
return self.countNodes(root.left) + self.countNodes(root.right) + 1
def find_left_depth(self, root):
if not root:
return 0
return self.find_left_depth(root.left) + 1
def find_right_depth(self, root):
if not root:
return 0
return self.find_right_depth(root.right) + 1- Time Complexity: O(h).
- Space Complexity: O(1).
where h is the height of the tree.