【算法训练-二叉树 六】【路径和计算】路径总和I、路径总和II、路径总和III、二叉树的最大路径和

import java.util.*;
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        return dfsFind(root, sum);
    }
    private boolean dfsFind(TreeNode node, int sum) {
        // 1 递归终止条件，节点为空，意味着越过了叶子节点，空节点没有路径
        if (node == null) {
            return false;
        }
        // 2 本级任务，减去当前节点的值，sum为接下来子树的目标值,同时判断是否到达叶子节点
        sum = sum - node.val;
        if (node.left == null && node.right == null) {
            return sum == 0 ? true : false;
        }
        // 3 返回值，返回子树的判断结果
        return dfsFind(node.left, sum) || dfsFind(node.right, sum);
    }
}

class Solution {
    // 1 设置结果集，并使用栈来记录完整路径
    List<List<Integer>> result = new LinkedList<List<Integer>>();
    Stack<Integer> path = new Stack<Integer>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfsFindPath(root, targetSum);
        return result;
    }
    public void dfsFindPath(TreeNode root, int targetSum) {
        // 1 如果越过叶子节点，则不满足条件
        if (root == null) {
            return;
        }
        // 2 路径添加当前节点值
        path.push(root.val);
        // 3 路径经过本级节点后目标值
        targetSum = targetSum - root.val;
        // 4 如果到达叶子节点，则进行判断，如果满足条件，则为寻找的目标路径
        if (root.left == null && root.right == null && targetSum == 0) {
            result.add(new LinkedList<Integer>(path));
        }
        // 5 没有找到，递归的从左右子树找
        dfsFindPath(root.left, targetSum);
        dfsFindPath(root.right, targetSum);
        // 6 因为path是引用类型，所有到达叶子节点无论是否找到，都要退出当前路径进入自己上层路径进行新的路径搜素哦
        path.pop();
    }
}

1
     /  \
    2    3
   / \    \
  4   5    6      节点4的前缀和为：1 + 2 + 4 = 7
 / \   \
7   8   9         节点8的前缀和：1 + 2 + 4 + 8 = 15  节点9的前缀和：1 + 2 + 5 + 9 = 17

假如题目给定数值为5
                     1     节点1的前缀和为: 1
                    / 
                   2    
                  / 
                 3         节点3的前缀和为: 1 + 2 + 3 = 6
                / 
               4  
prefix(3) - prefix(1) == 5,  所以 节点1 到 节点3 之间有一条符合要求的路径( 2 --> 3 )

1    前缀和为1
     / 
    0      前缀和为1
   /
  2        前缀和为3
 路径和为2的路径总数有：prefix(2) - prefix(1) 对应路径：0-2
                       prefix(2) - prefix(0) 对应路径：2

0
     /  \
    A:2  B:2
   / \    \
  4   5    6
 / \   \
7   8   9

/**
 * 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 {
    // 1 定义前缀和Map，key为前缀和，value为该前缀和的路径总数
    private Map<Long, Integer> prefixMap = new HashMap<Long, Integer>();
    // 2 定义结果集
    private Integer result = 0;
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        //  这是一个初态，一个节点到根节点的路径和就是节点的前缀和减去0，没有这个的话所有到根节点的符合条件的路径都无法找到，
        //  例如：1-3，找到路径和为4的，此时preSum(3)-4=preSum(0),如果没有preSum(0)为1条路径，就1条都招不到了
        prefixMap.put(0L, 1);
        dfsFindPath(root, 0L, targetSum); //传入参数是根节点root，和root之前的前缀和0。
        return result;
    }
    // 递归查找满足条件的路径和
    private void dfsFindPath(TreeNode node, long  prefixSum, int targetSum) {
        // 1 查找到空节点，返回
        if (node == null) {
            return;
        }
        // 2 记录当前节点前缀和
        prefixSum = prefixSum + node.val;
        // 如果之前出现过符合条件的前缀和，则记录+N
        result = result + prefixMap.getOrDefault(prefixSum - targetSum, 0);
        // 更新路径上当前节点前缀和的个数：把当前节点的前缀和也加入到哈希表中，如果已经存在了就给value + 1
        prefixMap.put(prefixSum, prefixMap.getOrDefault(prefixSum, 0) + 1);
        // 3 再去遍历其左右子树继续记录前缀和并找可行路径。
        dfsFindPath(node.left, prefixSum,targetSum); 
        dfsFindPath(node.right, prefixSum, targetSum);
        // 4 当自己的子树都寻找完毕后，需要把本级的前缀和去掉，返回上一层级
        prefixMap.put(prefixSum, prefixMap.get(prefixSum) - 1); 
    }
}

-10
   / \
  9  20
    /  \
   15   7

/**
 * 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 {
    // 1 设置最大路径总和并初始化
    private int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfsFindBestPath(root);
        return maxSum;
    }
    // 返回贡献值较大的节点总和
    private int dfsFindBestPath(TreeNode node) {
        // 1 到达空节点，越过叶子节点，贡献为0
        if (node == null) {
            return 0;
        }
        // 2 计算当前节点总值，分别获取左右子树贡献值,如果和为负数，则舍弃
        int leftValue = Math.max(dfsFindBestPath(node.left), 0);
        int rightValue = Math.max(dfsFindBestPath(node.right), 0);
        int curSumValue = node.val + leftValue + rightValue;
        // 3 maxSum与当前节点总值比较并重设最大值
        maxSum = Math.max(maxSum, curSumValue);
        // 4 设置当前节点最大值并返回，因为路径不能两边都走
        return node.val + Math.max(leftValue, rightValue);
    }
}