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.
Solutions
Solution 1: Recursion
We recursively traverse the entire tree and count the number of nodes.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the number of nodes in the tree.
1 2 3 4 5 6 7 8 91011
# 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 = rightclassSolution:defcountNodes(self,root:Optional[TreeNode])->int:ifrootisNone:return0return1+self.countNodes(root.left)+self.countNodes(root.right)
1 2 3 4 5 6 7 8 91011121314151617181920212223
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicintcountNodes(TreeNoderoot){if(root==null){return0;}return1+countNodes(root.left)+countNodes(root.right);}}
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funccountNodes(root*TreeNode)int{ifroot==nil{return0}return1+countNodes(root.Left)+countNodes(root.Right)}
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */publicclassSolution{publicintCountNodes(TreeNoderoot){if(root==null){return0;}return1+CountNodes(root.left)+CountNodes(root.right);}}
Solution 2: Binary Search
For this problem, we can also take advantage of the characteristics of a complete binary tree to design a faster algorithm.
Characteristics of a complete binary tree: leaf nodes can only appear on the bottom and second-to-bottom layers, and the leaf nodes on the bottom layer are concentrated on the left side of the tree. It should be noted that a full binary tree is definitely a complete binary tree, but a complete binary tree is not necessarily a full binary tree.
If the number of layers in a full binary tree is $h$, then the total number of nodes is $2^h - 1$.
We first count the heights of the left and right subtrees of $root$, denoted as $left$ and $right$.
If $left = right$, it means that the left subtree is a full binary tree, so the total number of nodes in the left subtree is $2^{left} - 1$. Plus the $root$ node, it is $2^{left}$. Then we recursively count the right subtree.
If $left > right$, it means that the right subtree is a full binary tree, so the total number of nodes in the right subtree is $2^{right} - 1$. Plus the $root$ node, it is $2^{right}$. Then we recursively count the left subtree.
The time complexity is $O(\log^2 n)$.
1 2 3 4 5 6 7 8 9101112131415161718192021
# 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 = rightclassSolution:defcountNodes(self,root:Optional[TreeNode])->int:defdepth(root):d=0whileroot:d+=1root=root.leftreturndifrootisNone:return0left,right=depth(root.left),depth(root.right)ifleft==right:return(1<<left)+self.countNodes(root.right)return(1<<right)+self.countNodes(root.left)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funccountNodes(root*TreeNode)int{ifroot==nil{return0}left,right:=depth(root.Left),depth(root.Right)ifleft==right{return(1<<left)+countNodes(root.Right)}return(1<<right)+countNodes(root.Left)}funcdepth(root*TreeNode)(dint){for;root!=nil;root=root.Left{d++}return}