113. Path Sum II - Medium

前往題目

想法

• 需要有額外的儲存空間存放每個node為止的sum，防止重複運算，我想hashtable應該可以
• 或是這題可能可以用backtracking，這樣也能記錄路徑

思路

1. dfs檢查每一條路徑
2. 到leaf後返回時要從path刪掉最後的node(backtracking)

Code

還算是有想出來，使用backtracking，邏輯部分有點小bug

參考了這個解答

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        res = new ArrayList<>();
        // Check root validity
        if (root == null) return res;
        // Start looking
        dfs(root, targetSum, new ArrayList<Integer>(), 0);
        return res;
    }

    private void dfs(TreeNode node, int targetSum, List<Integer> path, int sum) {
        // Reached the end
        if (node == null) return;

        // Record current node values sum
        sum += node.val;
        // Add current node to the path
        path.add(node.val);

        // Check left and right
        dfs(node.left, targetSum, path, sum);
        dfs(node.right, targetSum, path, sum);

        // Check is leaf and same with the targetSum
        if (node.left == null && node.right == null && sum == targetSum) {
            res.add(new ArrayList<>(path));
        }
        
        // Remove the last node to maintain correct path
        path.remove(path.size() - 1);
    }
}

2024/04/26

• 寫出了大部分，dfs一點點邏輯錯誤