# My Answer with my Solution Description

• The very first step is to understand what is a complete tree, coz it really take me some time to understand the description in English...

Once you know what is a complete tree, you will find it's feature could help you avoid a huge work of iterating.

let's say, a tree like below: if we go from top, we find the left-side depth and it's right-side depth is different,
in this case, we can iterate the function with both side: for left node B, wow, by compare the left depth and right depth, it is a full tree since Node B, so we could just return it with the full-tree Node number, which is
pow(2,0) +...+pow(2, depth), and when iterate back to Node C, not a full tree again, then iterate in second time to F and G.....

1. ------------A-----------------
2. ------B--------------C-------
3. ---D-----E---------F----G---
4. -H--I---J--K-----L-----------

.

The coding part could be very neat and clearly: (Hope it helps :)

``````public class Solution {
public int countNodes(TreeNode root) {
if(root == null){
return 0;
}else{
int x = leftdepth(root);
int y = rightdepth(root);
if(x != y){
return 1+countNodes(root.left)+countNodes(root.right);
}else{
int temp=0;
for(int i=0;i<=x;i++){
temp = temp+(int)Math.pow(2,i);
}
return temp;
}
}
}

public int rightdepth(TreeNode root){
int x=0;
if(root==null){
return 0;
}while(root.right!=null){
x = x+1;
root = root.right;
}
return x;
}

public int leftdepth(TreeNode root){
int x = 0;
if(root==null){
return 0;
}
while(root.left!=null){
x++;
root = root.left;
}
return x;
}
``````

}

• based on your idea, here is a shorter solution.

``````public class Solution {
public int countNodes(TreeNode root) {

if (getDepth(root,true)==getDepth(root,false))
{
return (int)(Math.pow(2,getDepth(root,true)))-1;
}
else
{
return countNodes(root.left)+countNodes(root.right)+1;
}
}

// isLeft=true, get left depth, isLeft=false, get rigth depth
public int getDepth(TreeNode root, boolean isLeft)
{int level =0;
while(root!=null)
{level++;
if(isLeft)
root=root.left;
else root=root.right;
}
return level;
}
}``````

using a queue, still use getDepth from top to bottom,

1. get a node from queue, if it has leftDepth==rigthDepth, total+=pow(2,depth)-1;
2. else, total+=1; put node.left, node.right into queue

• Your code is no longer accepted and would cause TLE.

• When x== y, try bit left shift like return (2 << x)-1 to compute the number of nodes. Just replace the code for computing temp with this.

• The recursive solve seem to be much worse than the iterative solve

• sounds it should work.

• Yes, This method is TLE

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