437. Path Sum III

DFS - brute force

把所有子樹都計算一次, 所以跑 以根為起點的樹 ＋ 以左子樹根為起點的樹 ＋ 以右子樹根為起點的樹

因為這樣就變成嵌套的走訪

所以 time : 最差 O(n^2), BST: O(nlogn)

space: O(n)

/**
 * 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 int pathSum(TreeNode root, int targetSum) {
        // DFS all the sub trees, and cal them all
        if (root == null) return 0;
        
        // 注意, 第一個 root 去叫 helper, 另兩個是嵌套, 又呼叫了本身
        // 所以會不斷地嵌套... 
        return helper(root, targetSum) + 
            pathSum(root.left, targetSum) + 
            pathSum(root.right, targetSum); 
    }
    
     private int helper(TreeNode node, int sum) {
        if (node == null) return 0;
         // 不用root to leaf, 所以不用 root.left == null && root.right == null 的條件
        return (node.val == sum ? 1 : 0) 
            + helper(node.left, sum - node.val) + helper(node.right, sum - node.val);
    }
}

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        return dfs(root, targetSum) + 
            pathSum(root.left, targetSum) + 
            pathSum(root.right, targetSum);
    }
    private int dfs(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        int leftCount = dfs(root.left, sum - root.val);
        int rightCount = dfs(root.right, sum - root.val);
        return (sum == root.val ? 1 : 0) + leftCount + rightCount;
    }
}

2. HashMap(presum, path count) + backtracking

如何不走訪所有的 subtree?

use memories 的技巧,

以 10, 5, 3 這例子, 走訪時計算 presum & path count

(10,1), (15,1), 18 走到 18

(18 - target(8)) = 10 exists in map , 代表有路徑符合我們的 targetSum

so path count = map.get(10)'; map's count record how many path sum count we have

then recursive do node.left & node.right

所以就假設以目前的 sum, 去走左右, 所以先 map sum, count+1

map.put(sum, map.getOrDefault(sum, 0)+1);

dfs(root.left, targetSum, map, sum);
dfs(root.right, targetSum, map, sum);

最後在 backtracking 回來

at last, need to do a backtracking, remove the last count

map.put(curSum, map.get(curSum) - 1);

Path Sum III - LeetCodeLeetCode

idea like subarray sum equals k, just this one is tree style

time: O(n)

space: O(n)

class Solution {
    // use hash map to store map(presum, count)
    // presum, if map.get(presum - target) exists, retirive the count(it's the correct path)
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // zero sum, 也是一個 count, 起點, 要注意, 不然有些。case 會有問題 
        return helper(root, 0, targetSum, map);
    }
    private int helper(TreeNode node, int curSum, int targetSum, Map<Integer, Integer> map) {
        if (node == null) return 0;

        curSum += node.val;
        int count = map.getOrDefault(curSum - targetSum, 0);
        
        map.put(curSum, map.getOrDefault(curSum, 0) + 1); // try backtracking
        
        count += helper(node.left, curSum, targetSum, map);
        count += helper(node.right, curSum, targetSum, map);
        
        map.put(curSum, map.get(curSum) - 1); // do backtracking
        return count;
    }
}

global variable

class Solution {
    int count = 0;
    public int pathSum(TreeNode root, int targetSum) {
        
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        dfs(root, targetSum, map, 0);
        return count;
    }

    private void dfs(TreeNode root, int targetSum, Map<Integer, Integer> map, int sum) {
        if (root == null) {
            return;
        }
        sum += root.val; // but why use same sum work? becase dfs will go back to upper level
        count += map.getOrDefault(sum - targetSum, 0);
        
        map.put(sum, map.getOrDefault(sum, 0)+1);
        
        dfs(root.left, targetSum, map, sum);
        dfs(root.right, targetSum, map, sum);
        
        map.put(sum, map.get(sum) -1); // notice map backtracking
    }
}

/*

find num of path sum equal to targetSum

map(sum, count)

ex:
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3

map(10, 1)
18 - 8 find in map => count += map(10, 1)

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

       5,
   4,      8,
 11,null,        13,4,
7,2, null,null, 5,1


0,1
5,1

5 4 11 2 = 22 find in (0,1)

27 -22 = 5 find in (5,1)
27 -22 = 5 find in (5,1)

*/

dfs sum can show all the sum in a tree

private void dfs(TreeNode root, int targetSum, Map<Integer, Integer> map, int sum) {
        if (root == null) {
            return;
        }
        sum += root.val; // but why use same sum work? becase dfs will go back to upper level
        System.out.println(sum);