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写这种题都一堆毛

宝宝