Easy java solution (but a bit long)

• ``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int countNodes(TreeNode root) {
int hl = leftHeight(root);
int hr = rightHeight(root);
if (hl == hr) {
return pow(hl) - 1;
} else {
// must be that hl = hr +1

// if the left child tree is "full"
if (rightHeight(root.left) +1 == hl)
return pow(hl-1)-1 + 1 + countNodes(root.right);
else
return countNodes(root.left) + 1 + pow(hr-1)-1 ;
}

}

// 2 to the power of n
int pow(int n) {
int result = 1;
while(n>0) {
result *=2; n--;
}
return result;
}

int leftHeight(TreeNode root) {
int l = 0;
while(root !=null) {
l++;
root = root.left;
}
return l;
}
int rightHeight(TreeNode root) {
int l = 0;
while(root !=null) {
l++;
root = root.right;
}
return l;
}

}``````

• it may not have the best performance ，but do have the most clear thoughts ，thank u ！

• interesting is that if use Math.pow(), will get TLE. Use public int
pow(int n) {
return 1<<n;
}
will improve time complexity a lot

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.