刷题-二叉树
2022-06-09  学习

二叉树的题,递归要熟悉

  • 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,用全局变量