作者yam276 (史萊哲林的優等生)
標題[閒聊] 每日leetcode 75 - Day19
時間2025-06-27 13:55:38
1372. Longest ZigZag Path in a Binary Tree
題目：
求一棵樹最長 Z 字形路徑長度
(左右左右走的最長長度)
思路：
設定一個狀態 is_right 來判斷上一輪是左還右
是相反就回 curr_len + 1 不是就回 1
Code:
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn longest_zig_zag(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
fn dfs(
node: Option<Rc<RefCell<TreeNode>>>,
max_len: &mut i32,
curr_len: i32,
is_right: bool,
) {
match node {
Some(rc_node) => {
let n = rc_node.borrow();
*max_len = (*max_len).max(curr_len);
dfs(
n.left.clone(),
max_len,
if !is_right { curr_len + 1 } else { 1 },
true,
);
dfs(
n.right.clone(),
max_len,
if is_right { curr_len + 1 } else { 1 },
false,
);
}
None => (),
}
}
let mut max_len = 0;
dfs(root.clone(), &mut max_len, 0, true);
dfs(root.clone(), &mut max_len, 0, false);
max_len
}
}
--
※ 發信站: 批踢踢實業坊(ptt-web.org.tw), 來自: 114.32.48.170 (臺灣)
※ 文章網址: https://ptt-web.org.tw/Marginalman/M.1751003740.A.152
→ Firstshadow: 大師 06/27 13:55
推 DJYOSHITAKA: 我好羨慕你 06/27 13:58
→ yam276: 來學 06/27 13:58