Get wrong answers! Can someone point me the mistakes in my code ?


  • 0
    Y
     public boolean hasPathSum(TreeNode root, int sum) {
        boolean result = false;
        if(root!=null){  // not empty tree
        int rootsum = root.val;
        if(root.left==null&&root.right==null){ // base case a leaf
            if(rootsum==sum){
                result = true;
            }
        }
        else if(root.left!=null){ // left subtree not empty
            sum = sum - rootsum;
            result = hasPathSum(root.left,sum);
            sum = sum + rootsum; // restore sum
        }
        else if(!result&&root.right!=null){ // if not found in left subtree try right subtree 
            sum = sum - rootsum;
            result = hasPathSum(root.right,sum);
        }
    }
     return result;
    

    }


  • 4
    M

    The second "else if" will only be considered if the first is evaluated to false (root.left is null). If it is not null, but simply does not have the given path, it will enter the first "else if," do the calculations, and then return the result, never attempting the right child. The result of this is that only the leftmost path is ever checked.

     public boolean hasPathSum(TreeNode root, int sum) {
        boolean result = false;
        if(root!=null){  // not empty tree
        int rootsum = root.val;
        if(root.left==null&&root.right==null){ // base case a leaf
            return rootsum == sum;
        }
        sum -= rootsum;
    
        if(root.left!=null){ // left subtree not empty
            result = hasPathSum(root.left,sum);
        }
        if(!result&&root.right!=null){ // if not found in left subtree try right subtree 
            result = hasPathSum(root.right,sum);
        }
    }
     return result;
    

    Technically, thanks to the very first "if," the "root.left/right != null" is unneeded, as it will evaluate to false and continue on. Therefore, it can be simplified to:

     public boolean hasPathSum(TreeNode root, int sum) {
        if(root!=null){  // not empty tree
            int rootsum = root.val;
            if(root.left==null&&root.right==null){ // base case a leaf
                return rootsum == sum;
            }
            sum -= rootsum;
            return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
        }
        return false;
    }
    

  • 0
    Y

    Thanks!! very elegant code


Log in to reply
 

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