Approach 1: Linear Time O(N)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
28
29
30
31
32
33
34
35
36
37
38
39
40/**
* 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;
* }
* }
*/
class Solution {
public int countNodes(TreeNode root) {
return root==null?0:1+countNodes(root.left)+countNodes(root.right);
}
}
/*
class Solution {
int cnt=0;
private void util(TreeNode root){
if(root==null) return;
if(root.left!=null){
cnt++;
util(root.left);
}
if(root.right!=null){
cnt++;
util(root.right);
}
}
public int countNodes(TreeNode root) {
if(root==null) return cnt;
util(root);
return cnt+1;
}
}*/
Approach 2: Binary search: {binary search in binary search O(d^2)=O(log^2 N)}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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67/**
* 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;
* }
* }
*/
class Solution {
// Return tree depth in O(d) time
private int computeDepth(TreeNode node){
int d=0;
while(node.left!=null){
node=node.left;
d++;
}
return d;
}
// Last level nodes are enumerated from 0 to 2^d - 1 (left -> right).
// Return True if last level node idx exists.
// Binary search with O(d) complexity.
private boolean exits(int idx,int d,TreeNode node){
int left=0,right=(int)Math.pow(2,d)-1;
int pivot;
for(int i=0;i<d;i++){
pivot=left+(right-left)/2;
if(idx<=pivot){
node=node.left;
right=pivot;
}else{
node=node.right;
left=pivot+1;
}
}
return node!=null;
}
public int countNodes(TreeNode root) {
// if the tree is empty
if(root==null) return 0;
int d=computeDepth(root);
// if the tree contains 1 node
if(d==0) return 1;
// Last level nodes are enumerated from 0 to 2^d - 1 (left -> right).
// Perform binary search to check how many nodes exist.
int left=0,right=(int)Math.pow(2,d)-1;
int pivot;
while(left<=right){
pivot=left+(right-left)/2;
if(exits(pivot,d,root)) left=pivot+1;
else right=pivot-1;
}
// The tree contains 2^d - 1 nodes on the first (d - 1) levels
// and left nodes on the last level.
return (int)Math.pow(2,d)-1+left;
}
}