Skip to main content

rustgym/leetcode/
_1372_longest_zigzag_path_in_a_binary_tree.rs

1struct Solution;
2use rustgym_util::*;
3
4trait Postorder {
5    fn postorder(&self, max: &mut i32) -> (i32, i32);
6}
7
8impl Postorder for TreeLink {
9    fn postorder(&self, max: &mut i32) -> (i32, i32) {
10        if let Some(node) = self {
11            let node = node.borrow();
12            let (_, left_right) = node.left.postorder(max);
13            let (right_left, _) = node.right.postorder(max);
14            let left = left_right + 1;
15            let right = right_left + 1;
16            *max = (*max).max(left);
17            *max = (*max).max(right);
18            (left, right)
19        } else {
20            (0, 0)
21        }
22    }
23}
24
25impl Solution {
26    fn longest_zig_zag(root: TreeLink) -> i32 {
27        let mut res = 0;
28        root.postorder(&mut res);
29        res - 1
30    }
31}
32
33#[test]
34fn test() {
35    let root = tree!(
36        1,
37        None,
38        tree!(
39            1,
40            tree!(1),
41            tree!(1, tree!(1, None, tree!(1, None, tree!(1))), tree!(1))
42        )
43    );
44    let res = 3;
45    assert_eq!(Solution::longest_zig_zag(root), res);
46    let root = tree!(
47        1,
48        tree!(1, None, tree!(1, tree!(1, None, tree!(1)), tree!(1))),
49        tree!(1)
50    );
51    let res = 4;
52    assert_eq!(Solution::longest_zig_zag(root), res);
53    let root = tree!(1);
54    let res = 0;
55    assert_eq!(Solution::longest_zig_zag(root), res);
56}