1448. Count Good Nodes in Binary Tree
題目：
子節點比上一個父節點大
就是好寶寶節點
求有幾個好寶寶節點
思路：
標準的 dfs 題目
一直把左右子節點跟目前節點的 val 往下傳
讓 dfs 回傳好寶寶節點數量
count = count + dfs(左節點) + dfs(右節點)
有個細節
if let Some(rc_root) = root.clone() {
dfs(Some(rc_root.clone()), rc_root.borrow().val)
} else {
0
}
這邊是先取 Some
再包進 Some 放進 dfs
為了避免所有權轉移使用 .clone()
使用 .clone() 只會複製指標 開銷很小
.borrow().val 則是 Rc 借用的部分
可以當成 我要借玩具給朋友玩
但我不是送他 所以我沒有給他玩具的所有權
因此使用 .clone() 確保他每次都是來我家拿東西玩
另外這一題因為沒要求改變內容
所以使用 .clone() 與 .borrow() 與存取不會有問題的 i32 型態來避免問題
全部都是沒改變所有權以及都是不可變借用
(要改變要使用 .borrow_mut())
Code:
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn good_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
fn dfs(node: Option<Rc<RefCell<TreeNode>>>, max_val: i32) -> i32 {
match node {
Some(rc_node) => {
let node_ref = rc_node.borrow();
let mut count = 0;
if node_ref.val >= max_val {
count += 1;
}
let new_max = max_val.max(node_ref.val);
count += dfs(node_ref.left.clone(), new_max);
count += dfs(node_ref.right.clone(), new_max);
count
}
None => 0,
}
}
if let Some(rc_root) = root.clone() {
dfs(Some(rc_root.clone()), rc_root.borrow().val)
} else {
0
}
}
}

你好厲害

大師

笨色Rust寫這種題都一堆毛

寶寶