Why my code is wrong answer


  • 1
    J

    public class Solution {
    public int maxDepth(TreeNode root) {

     LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
     TreeNode p;
     if(root==null) return 0;
     root.val=1;
     queue.add(root);
     int height=0;
     while(!queue.isEmpty())
     {
         p=queue.getFirst();
     
         if(p.left!=null)
         {
             
             p.left.val=p.val+1;
             queue.add(p.left);
            
         }
         else if(p.right!=null)
         {
           
            p.right.val=p.val+1;
             queue.add(p.right);
         
         }
         height=p.val; 
         queue.removeFirst();
     }
     return (height);
    

    }

    }


  • 1
    V

    In the above program inside the while loop in the second if statement else if is used, but one need to indeed check for both the conditions as whether left node is null or right node is null.

    Consider the sample input case {3,9,20,#,#,15,7} node 3 has child nodes as 9 and 20, above program in the first iteration of while loop only increments the height of node 9 but not node 20 because left node of 3 (which is 9) is not null, second if block doesn't get executed, the same goes on with next iteration. To get correct Depth of binary tree inside the while loop just replace else if statement with if statement.

    public class Solution 
    { 
        public int maxDepth(TreeNode root)
        {
             LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
             TreeNode p;
             if(root==null) return 0;
             root.val=1;
             queue.add(root);
             int height=0;
             while(!queue.isEmpty())
             {
                 p=queue.getFirst();
            
                 if(p.left!=null)
                 {
            
                     p.left.val=p.val+1;
                     queue.add(p.left);
            
                 }
                 if(p.right!=null)
                 {
            
                    p.right.val=p.val+1;
                     queue.add(p.right);
            
                 }
                 height=p.val; 
                 queue.removeFirst();
            }
        return (height);
        }
    }
    

  • 0
    A

    by your code, it will accumulate the depth on a sub tree, instead of the whole tree.


  • 0
    V

    Above program finds the depth of whole tree.


  • 0
    L

    @james this is a breadth first search,so this runs until last level of the tree is reached and hence gives the height of the whole tree.


Log in to reply
 

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