Binary tree longest consecutive sequence ii

Tree Depth-First Search Binary Tree

50.1% acceptance

Mar 31, 2026

1202

104

Given the root of a binary tree, return the length of the longest consecutive path in the tree. A consecutive path is a path where the values of the consecutive nodes in the path differ by one. 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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn longest_consecutive(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    let mut ans = 0;
    Self::dfs(&root, &mut ans);
    ans
  }
  
  // Returns (increasing length ending at node, decreasing length ending at node)
  fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, ans: &mut i32) -> (i32, i32) {
    if let Some(n) = node {
      let b = n.borrow();
      let (mut inc, mut dec) = (1, 1);
      let (li, ld) = Self::dfs(&b.left, ans);
      let (ri, rd) = Self::dfs(&b.right, ans);
      if let Some(ref left) = b.left {
        let lv = left.borrow().val;
        if lv == b.val + 1 { inc = inc.max(li + 1); }
        if lv == b.val - 1 { dec = dec.max(ld + 1); }
      }
      if let Some(ref right) = b.right {
        let rv = right.borrow().val;
        if rv == b.val + 1 { inc = inc.max(ri + 1); }
        if rv == b.val - 1 { dec = dec.max(rd + 1); }
      }
      *ans = (*ans).max(inc + dec - 1);
      (inc, dec)
    } else {
      (0, 0)
    }
  }
}