Gettng TLE for a lengthy test case in machine grader.Let me know where it went wrong.


  • 0
    S
    public class Solution {
        public int countNodes(TreeNode root) 
        {
            
                return count1(root,0);
            
        }
        public int getHeight(TreeNode root)
    	{
    		if(root==null)
    		{
    			return 0;
    		}
    		else if(root.left==null && root.right==null)
    		{
    			return 1;
    		}
    		else
    		{
    			int sum1 = 1+getHeight(root.left);
    			int sum2 = 1+getHeight(root.right);
    			return (sum1>=sum2?sum1:sum2);
    		}
    		
    	}
    	public int count1(TreeNode root,int sum)
    	{
    		if(root==null)
    		{
    			return 0;
    		}
    		else if(root.left==null && root.right==null)
    		{
    			return sum=sum+1;
    		}
    		else
    		{
    			int lh = getHeight(root.left);
    			int rh = getHeight(root.right);
    			
    				if(lh-rh==0)
    				{
    					sum += (int) (Math.pow(2, lh)-1)+1;
    					sum = count1(root.right,sum);
    				}
    				else
    				{
    					sum += (int) (Math.pow(2,rh)-1)+1;
    					sum = count1(root.left,sum);
    				}
    			
    		}
    		return sum;
    	}

  • 1

    Already your getHeight alone is O(n). Make it O(log n). And you might have to replace Math.pow with something faster.


  • 0
    S

    Thanks for your review.I made changes got it accepted:)


Log in to reply
 

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