Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree.
Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid. On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.
Example 1:
Input:
1
/ \
2 3
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].
Example 2:
Input:
2
/ \
1 3
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].
Note: All the values of tree nodes are in the range of [-1e7, 1e7].
struct Solution;
use rustgym_util::*;
trait Postorder {
fn postorder(&self, max: &mut usize) -> Option<(i32, usize, usize)>;
}
impl Postorder for TreeLink {
fn postorder(&self, max: &mut usize) -> Option<(i32, usize, usize)> {
if let Some(node) = self {
let node = node.borrow();
let val = node.val;
let mut inc = 1;
let mut dec = 1;
if let Some((lval, linc, ldec)) = node.left.postorder(max) {
if lval + 1 == val {
inc = inc.max(linc + 1);
}
if lval - 1 == val {
dec = dec.max(ldec + 1);
}
}
if let Some((rval, rinc, rdec)) = node.right.postorder(max) {
if rval + 1 == val {
inc = inc.max(rinc + 1);
}
if rval - 1 == val {
dec = dec.max(rdec + 1);
}
}
*max = (*max).max(inc + dec - 1);
Some((val, inc, dec))
} else {
None
}
}
}
impl Solution {
fn longest_consecutive(root: TreeLink) -> i32 {
let mut res = 0;
root.postorder(&mut res);
res as i32
}
}
#[test]
fn test() {
let root = tree!(1, tree!(2), tree!(3));
let res = 2;
assert_eq!(Solution::longest_consecutive(root), res);
let root = tree!(2, tree!(1), tree!(3));
let res = 3;
assert_eq!(Solution::longest_consecutive(root), res);
}