题解 | #二叉树中和为某一值的路径(三)#

• 将树拆成一层一层增加的前缀和

1. 1，1 --- 前缀和为1出现1次。检查current_sum - target = -5
2. 1+2，1----前缀和为3出现一次。检查 current_sum - target = -3
3. 1+2+4，1---前缀和为7出现一次。检查current_sum - target = 1，并且1的前缀和在map出现过，说明把1前缀和代表的一连续节点去掉后，的一连续节点就是满足的路径。----并且1的前缀和出现多少次，就证明有多少条路径。
4. 往上回溯的时候，要将当前节点的前缀和减少----*prefix_sum.entry(current_sum).or_insert(0) -= 1

/**
 * #[derive(PartialEq, Eq, Debug, Clone)]
 * pub struct TreeNode {
 *     pub val: i32,
 *     pub left: Option<Box<TreeNode>>,
 *     pub right: Option<Box<TreeNode>>,
 * }
 *
 * impl TreeNode {
 *     #[inline]
 *     fn new(val: i32) -> Self {
 *         TreeNode {
 *             val: val,
 *             left: None,
 *             right: None,
 *         }
 *     }
 * }
 */
struct Solution{

}
use std::collections::HashMap;
impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param root TreeNode类 
        * @param sum int整型 
        * @return int整型
    */
    pub fn FindPath(&self, root: Option<Box<TreeNode>>, sum: i32) -> i32 {
        let mut prefix_sum = HashMap::new();
        prefix_sum.insert(0, 1); // 前缀和为0的路径数量为1
        self.dfs(&root, sum, 0, &mut prefix_sum)
    }
    
    fn dfs(&self, root: &Option<Box<TreeNode>>, target: i32, current_sum: i32, prefix_sum: &mut HashMap<i32, i32>) -> i32 {
        if let Some(node) = root {
            let current_sum = current_sum + node.val;
            let mut count = *prefix_sum.get(&(current_sum - target)).unwrap_or(&0);
            *prefix_sum.entry(current_sum).or_insert(0) += 1;
            count += self.dfs(&node.left, target, current_sum, prefix_sum);
            count += self.dfs(&node.right, target, current_sum, prefix_sum);
            *prefix_sum.entry(current_sum).or_insert(0) -= 1;
            count
        } else {
            0
        }
    }
}