[leetcode] PathSum

Leetcode PathSum

문제는 간단했다. DFS 알고리즘을 통해 해결하면되는 문제였다. DFS를 재귀함수를 통해 구현하면 된다!

그런데 한 가지 잘 못 생각한 것이 있다.

• root.val 값들을 더 해가며 Target 값과 일치하는 값이 있으면 True를 리턴해주면 되겠다. 서치를 내려갈 때마다 root.val 값들을 더 해 나간다고 생각하는 순간부터 생각이 잘 못되었다. 그렇게 되면 값이 false 일 때 거슬러 올라오면서 다시 값을 빼줘야 하는데 복잡해진다.

가장 쉬운 방법은 재귀를 호출할 때 target 값에서 루트 값을 제외한 나머지를 다시 밑에 타겟으로 내리는 것이다. 구현된 코드는 아래와 같다.

    public boolean hasPathSum(TreeNode root, int targetSum) {

        if(root == null) return false;

        if(root.left == null && root.right == null && targetSum-root.val == 0) return true;

        return hasPathSum(root.left, targetSum-root.val) || hasPathSum(root.right, targetSum-root.val);
    }