112. Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

 

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true

 

재귀함수 사용하여 풀이

1. targetSum - 노드의 값이 0이면서 left, rigth가 null일 경우 -> 해당 케이스 존재 --> true

2. left null이 아니면 -> 왼쪽 노드로 이동후 재귀

3. right null이 아니면 -> 오른쪽 노드로 이동후 재귀

* root가 null인 케이스 처리

 

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        boolean ans = false;
        
        if(root == null)
            return false;
        int subSum = targetSum - root.val;
        if(subSum == 0 && root.left == null && root.right == null)
            return(ans = true);
        if(root.left != null)  
        // ans || hasPathSum... has no utility if the ans is false
            ans = ans || hasPathSum(root.left, subSum);       
      
        if(root.right != null) 
        // But if it is true then we can avoid calling hasPathSum
        // here as answer has already been found
            ans = ans || hasPathSum(root.right, subSum);   
        return(ans);
    }
    
}