Longest univalue path

Tree Depth-First Search Binary Tree

43.6% acceptance

Feb 20, 2026

4449

680

Given the root of a binary tree, return the length of the longest path where each node in the path has the same value (edges counted).

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn longest_univalue_path(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    let mut ans = 0;
    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, ans: &mut i32) -> i32 {
      match node {
        None => 0,
        Some(n) => {
          let b = n.borrow();
          let lp = dfs(&b.left, ans);
          let rp = dfs(&b.right, ans);
          let left_val = b.left.as_ref().map(|l| l.borrow().val);
          let right_val = b.right.as_ref().map(|r| r.borrow().val);
          let l_ext = if left_val == Some(b.val) { lp + 1 } else { 0 };
          let r_ext = if right_val == Some(b.val) { rp + 1 } else { 0 };
          *ans = (*ans).max(l_ext + r_ext);
          l_ext.max(r_ext)
        }
      }
    }
    dfs(&root, &mut ans);
    ans
  }
}