[LeetCode/112/Java]Path Sum

[LeetCode/112/Java]Path Sum

 

풀이

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return hasPathSum(root, targetSum, 0);
    }
    
    public boolean hasPathSum(TreeNode root, int targetSum, int sum) {
        if(root == null) return false;
        sum += root.val;
        if(root.left == null && root.right == null) {
            if(sum == targetSum) return true;
        }
        
        boolean result = false;
        if(root.left != null) result = hasPathSum(root.left, targetSum, sum);
        if(result == true) return result;
        if(root.right != null) result = hasPathSum(root.right, targetSum, sum);
        
        return result;
    }
}

후기

지정된 값이 root node(시작노드)에서부터 leaf node(끝 노드)까지 더한 값이 존재하는지를 확인하는 문제입니다.

같은 값이 존재하면 true를 리턴하고 없을 경우에는 false를 리턴합니다.

깊이 우선 탐색(DFS)가 빠를 것 같아서 해당 방식으로 풀이를 하였습니다.

 

time complexity O(N)
space complexity O(N)