298. Binary Tree Longest Consecutive Sequence

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

Example 1:

Input:

   1
    \
     3
    / \
   2   4
        \
         5

Output: 3

Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

Example 2:

Input:

   2
    \
     3
    / 
   2    
  / 
 1

Output: 2 

Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

Rust Solution

struct Solution;
use rustgym_util::*;

trait Postorder {
    fn postorder(&self, max: &mut usize) -> Option<(i32, usize)>;
}

impl Postorder for TreeLink {
    fn postorder(&self, max: &mut usize) -> Option<(i32, usize)> {
        if let Some(node) = self {
            let node = node.borrow();
            let val = node.val;
            let mut length = 1;
            if let Some(left) = node.left.postorder(max) {
                if val + 1 == left.0 {
                    length = length.max(left.1 + 1);
                }
            }
            if let Some(right) = node.right.postorder(max) {
                if val + 1 == right.0 {
                    length = length.max(right.1 + 1);
                }
            }
            *max = (*max).max(length);
            Some((val, length))
        } 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, None, tree!(3, tree!(2), tree!(4, None, tree!(5))));
    let res = 3;
    assert_eq!(Solution::longest_consecutive(root), res);
    let root = tree!(2, None, tree!(3, tree!(2, tree!(1), None), None));
    let res = 2;
    assert_eq!(Solution::longest_consecutive(root), res);
}

Having problems with this solution? Click here to submit an issue on github.