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