My problem of solution in Java


  • 0
    E

    My initial solution:
    public class Solution {

    public boolean hasPathSum(TreeNode root, int sum) {
        
        if(root == null) return false;
        if(root.left == null && root.right == null){
            return root.val == sum;
        }
        ***if(root.val>sum) return false;***
        return hasPathSum(root.left, sum-root.val)||hasPathSum(root.right, sum-root.val); 
        
    }
    

    }

    The error is
    Input: {-2,#,-3}, -5
    Output: false
    Expected: true

    But after I delete the line: if (root.val>sum) return false;
    I initially typed this line in order to make the code get result faster, but I don't know why I get the wrong answer. Is it because the appearance of the #? But why after I delete that line, the solution turns right?


  • 0
    Y

    Because the value of the TreeNode can be negative, thus the sum in each layer is not guaranteed to be monotonously ascending. Thus, if(root.val>sum) return false; will lead to failure.


  • 0
    Y

    The tricky point of this problem is that, because of the possible negative node value, unless you reach the leaf, you can not know whether it has a valid path or not.


Log in to reply
 

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