每日三题-二叉树的最大深度、二叉树中的最大路径和、路径总和III

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}

class Solution {
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        getMax(root);
        return res;
    }
    public int getMax(TreeNode root){
        if(root == null) return 0;
        int cur = root.val;
        // 获取左边的值,如果为负数则不取左边
        int left = Math.max(getMax(root.left),0);
        int right = Math.max(getMax(root.right),0);
        int sum = cur + left + right;
        res = Math.max(sum,res);
        // 取左右两边的大值返回给root的父节点使用
        return cur + Math.max(left,right);
    }
}

class Solution {
    //递归每一个节点
    public int pathSum(TreeNode root, int targetSum) {
        int res = 0;
        if(root == null) return 0;
        res+=sum(root,targetSum);
        res+=pathSum(root.left,targetSum);
        res+=pathSum(root.right,targetSum);
        return res;
    }

    // 注意这里要用long
    public int sum(TreeNode root,long targetSum){
        int res = 0;
        //递归结束条件
        if(root == null) return 0;
        
        //当前节点满足了res++;
        if(targetSum == root.val){
            res++;
        }

        //继续找左边
        res+=sum(root.left,targetSum-root.val);
        //找右边
        res+=sum(root.right,targetSum-root.val);
        return res;
    }
}

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

    // 注意这里要用long
    public int sum(TreeNode root,int targetSum,long curSum,HashMap<Long,Integer> map){
        int res = 0;
        //递归结束条件
        if(root == null) return 0;
        curSum = curSum+root.val;
        res+=map.getOrDefault(curSum-targetSum,0);
        map.put(curSum,map.getOrDefault(curSum,0)+1);
        //计算左右边
        res+=sum(root.left,targetSum,curSum,map);
        res+=sum(root.right,targetSum,curSum,map);
        //移除当前
        map.put(curSum,map.get(curSum)-1);
        return res;
    }
}