(Tree) Path Sum

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

트리를 DFS로 탐색하며 최대 합인 패스의 개수를 찾는 문제이다.

class Solution {

    int result = 0;

    private void traverse(TreeNode root, int s, List<TreeNode> nodes) {
        if (root == null) {
            return;
        }
//        System.out.println(root.val);

        for (int i = 0; i < nodes.size(); i++) {
            int sum = 0;

            for (int j = i; j < nodes.size(); j++) {
                sum += nodes.get(j).val;
            }

            if (sum == s) {
                result++;
            }
        }

        nodes.add(root.left);
        traverse(root.left, s, nodes);

        nodes.remove(root.left);
        nodes.add(root.right);

        traverse(root.right, s, nodes);
        nodes.remove(root.right);
    }

    public int pathSum(TreeNode root, int sum) {

        List<TreeNode> nodes = new ArrayList<>();
        nodes.add(root);
        traverse(root, sum, nodes);
//        traverse();

        return result;
    }
}

위의 방법은 시간복잡도가 좋지 않으니 아래처럼 구현하면 좋다.

class Solution {
    public int pathSum(TreeNode root, int sum) {
        if(root == null)
            return 0;
        return traverse(root, sum, 0) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    private int traverse(TreeNode root, int sum, int currentSum) {
        if(root == null)
            return 0;
        if(currentSum + root.val == sum)
            return 1 + traverse(root.left, sum, currentSum+root.val) 
                        + traverse(root.right, sum, currentSum+root.val);
        else 
            return traverse(root.left, sum, currentSum+root.val) 
                        + traverse(root.right, sum, currentSum+root.val);
    }
}