刷题-二叉树

二叉树的题，递归要熟悉

• 543，617，112

力扣437

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

    private int recur(TreeNode root, int target, Map<Long, Integer> map, Long curr){
        if(root == null){
            return 0;
        }
        curr += root.val;
        int count = map.getOrDefault(curr - target, 0);
        map.put(curr, map.getOrDefault(curr, 0) + 1);
        //map存储当前节点和祖先节点的前缀和，传给子节点
        count += recur(root.left, target, map, curr);
        count += recur(root.right, target, map, curr);
        //路径是向下的，回溯时要删除当前节点对应的前缀和
        map.put(curr, map.get(curr) - 1);
        return count;
    }
}

路径问题：求数量可以用前缀和，求所有结果还是dfs

• 109，用全局变量