[閒聊] 每日leetcode 75 - Day17
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
}
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.249.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1750782072.A.4D3.html
推
06/25 00:22,
5月前
, 1F
06/25 00:22, 1F
→
06/25 00:22,
5月前
, 2F
06/25 00:22, 2F
→
06/25 00:23,
5月前
, 3F
06/25 00:23, 3F
※ 編輯: yam276 (123.193.249.242 臺灣), 06/25/2025 00:24:05
推
06/25 00:24,
5月前
, 4F
06/25 00:24, 4F
推
06/25 08:25,
5月前
, 5F
06/25 08:25, 5F