Leetcode 112: path sum

link

subject ：

Ideas ：dfs

The idea is similar to Change for , Every time you recurse down , Add up the number you want sum Subtract the current node root Of val, In this way, we can get the money we need to collect from the next layer , Until the leaf node sum Node equal val Return true ！

The topic is about root node to leaf node ！ So we have to traverse to the end , Use post order traversal ;

Single layer node ： Determine whether it is currently a leaf node , Yes, judge sum and val Whether it is equal or not ; If it's not a leaf node , Continue to recursive ;

base case： If root==null ,return false;

class Solution {
    
    public boolean hasPathSum(TreeNode root, int sum) {
    
        //  You must go to the leaf node  ！
        //  You must traverse to the end ！ dfs
        //  Traversing to the leaf node is not equal to sum, Then return to false;
        if(root==null){
    
            return false;
        }
		//  Catch the result , to flash back 
        boolean left=hasPathSum(root.left,sum-root.val);
        boolean right=hasPathSum(root.right,sum-root.val);

        //  Current node :
        //  To the left and right null Is the leaf node ！
        if(root.left==null && root.right==null){
    
        //  Traverse to the end , here root value =sum  To return to true !
            return root.val==sum; 
        }
        return left || right;
    }
}