My Answer with my Solution Description


  • 2
    S

    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;
    }
    

    }


  • 0
    B

    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;
    }
    }

  • 0
    B

    what about iterative solution?
    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

  • 0
    W

    Your code is no longer accepted and would cause TLE.


  • 0
    N

    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.


  • 0
    F

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


  • 0
    R

    sounds it should work.


  • 0
    W

    Yes, This method is TLE


Log in to reply
 

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