[閒聊] 每日leetcode 75 - Day15

[yam276 (史萊哲林的優等生)]

104. Maximum Depth of Binary Tree


題目：

取得樹的深度


思路：

Rust 解樹的題目似乎都是用 Rc 包 RefCell

因為 Box 是唯一擁有者 所以當你訪問的時候會消耗所有權

這樣會破壞樹的結構


所以通常都用多所有權與動態借用的 Option<Rc<RefCell<TreeNode>>

當你對 Rc 進行 .clone() 的時候也不會複製資料

而只是複製指標 也會省資源


那這題目 dfs 用遞迴是最快的

走左走右 每次回傳 1 + 下一層次數

比較左右回來哪個大就選誰


Code:

use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        match root {
            None => 0,
            Some(node) => {
                let left_depth =
                        Solution::max_depth(node.borrow().left.clone());

                let right_depth =
                        Solution::max_depth(node.borrow().right.clone());

                1 + left_depth.max(right_depth)
            }
        }
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1750316494.A.877.html
※ 編輯: yam276 (60.248.143.163 臺灣), 06/19/2025 15:01:52
推 oin1104: 大師