楼主:
yam276 ('_')
2025-06-27 13:55:381372. 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
}
}