437. Path Sum III
題目：
找一棵樹上連續節點和等於 target 的數量
思路：
這題如果用暴力 dfs 遍歷
寫很快 但很慢 會變成 O(n^2)
可以用類似儲存狀態的方式
前綴和 + HashMap
就是你每次儲存前面節點的和
root, root+node1, root+node1+node2 這樣累積路徑和
那你用傳承下來的 curr_sum 去減這些節點
然後放進紀錄的 HashMap 找
就能直接獲得是否有符合答案的組合
記得要先更新 curr_sum 放進 HashMap 再跑下面節點
最後回來的時候會一層一層 把用過的節點扣掉 變成0就刪除
因為用 HashMap 是每個節點共同維護表 避免汙染
還有中間要轉 i64 計算
因為 i32 會在最後一個測資大爆炸==
Code:
use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;
impl Solution {
pub fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32)-> i32
{
fn dfs(
node: Option<Rc<RefCell<TreeNode>>>,
curr_sum: i64,
target: i32,
prefix: &mut HashMap<i64, i64>,
) -> i64 {
match node {
Some(rc_node) => {
let node = rc_node.borrow();
let curr_sum = curr_sum as i64 + node.val as i64;
let mut count = *prefix.get(&(curr_sum - target as i64))
.unwrap_or(&0);
*prefix.entry(curr_sum).or_insert(0) += 1;
count += dfs(node.left.clone(), curr_sum, target, prefix);
count += dfs(node.right.clone(), curr_sum, target, prefix);
let entry = prefix.get_mut(&curr_sum).unwrap();
*entry -= 1;
if *entry == 0 {
prefix.remove(&curr_sum);
}
count
}
None => 0,
}
}
let mut prefix = HashMap::new();
prefix.insert(0, 1);
dfs(root, 0, target_sum, &mut prefix) as i32
}
}

別卷了