Skip to main content

rustgym/leetcode/
_298_binary_tree_longest_consecutive_sequence.rs

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