[閒聊] 每日leetcode 75 - Day19
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.cc), 來自: 114.32.48.170 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1751003740.A.152.html
→
06/27 13:55,
5月前
, 1F
06/27 13:55, 1F
推
06/27 13:58,
5月前
, 2F
06/27 13:58, 2F
→
06/27 13:58,
5月前
, 3F
06/27 13:58, 3F