[leetcode #437] Path Sum III

Problem

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Example 2:

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

Constraints:

・ The number of nodes in the tree is in the range [0, 1000].
・ -10⁹ <= Node.val <= 10⁹
・ -1000 <= targetSum <= 1000

Idea

Tree의 합을 구하는 문제는 대부분 backtracking을 요구하는 것이 많다. Tree를 다루기 때문에 재귀함수를 사용하는 것이 일반적이며, 자식 노드를 탐색한 후 자식노드가 가지고 있던 값들을 지우며 처리하는 문제가 많다. Path Sum을 구하는 문제도 예외는 아니다.

Path의 값을 저장할 수 있는 자료구조가 필요한데, 나는 list를 사용했다. 나중에 곰곰히 생각해보니 HashMap을 사용하는 것이 O(1)이기 때문에 O(n)이 걸리는 list를 사용한 것이 어리석었다는 걸 알 수 있었다.

재귀함수는 다음과 같다.

1. node가 null인 경우 return
2. node의 값이 targetSum일 경우 count 1 증가
3. list에 저장되어 있는 값에 node의 값을 더해 targetSum과 일치할 경우 count 1 증가. list에 저장되어 있는 값을 node 값을 더한 값으로 치환.
4. node의 값도 list에 저장
5. 자식노드 탐색
6. 자식노드 값을 list에서 제거
7. list에 저장되어 있는 값을 자식노드의 값을 뺀 값으로 치환.

이 풀이를 보신 분은 List를 쓰지 말고 HashMap을 써서 풀기를!

Solution

class Solution {
    int ret = 0;

    public int pathSum(TreeNode root, int targetSum) {
        List<Integer> list = new ArrayList<Integer>();

        traverseTree(root, list, targetSum);

        return ret;
    }

    private void traverseTree(TreeNode node, List<Integer> list, int targetSum) {
        if (node == null)
            return;

        if (node.val == targetSum)
            ret++;

        for (int i=0; i < list.size(); i++) {
            int val = list.get(i);
            if (val + node.val == targetSum) {
                ret++;
            }
            list.set(i, val + node.val);
        }

        list.add(node.val);
        traverseTree(node.left, list, targetSum);
        traverseTree(node.right, list, targetSum);
        list.remove(list.size()-1);

        for (int i=0; i < list.size(); i++) {
            int val = list.get(i);
            list.set(i, val - node.val);
        }
    }
}

Reference

https://leetcode.com/problems/path-sum-iii/