-
Notifications
You must be signed in to change notification settings - Fork 229
/
L32_SizeOfATreeJava
34 lines (27 loc) · 926 Bytes
/
L32_SizeOfATreeJava
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
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
int left = getHeightLeft(root);
int right = getHeightRight(root);
//If left and right are equal it means that the tree is complete and hence go for 2^h -1.
if(left == right) return ((2<<(left)) -1);
//else recursively calculate the number of nodes in left and right and add 1 for root.
else return countNodes(root.left)+ countNodes(root.right)+1;
}
public int getHeightLeft(TreeNode root){
int count=0;
while(root.left!=null){
count++;
root = root.left;
}
return count;
}
public int getHeightRight(TreeNode root){
int count=0;
while(root.right!=null){
count++;
root = root.right;
}
return count;
}
}