Count univalue subtrees

Tree Depth-First Search Binary Tree

57.5% acceptance

Mar 31, 2026

1246

457

Given the root of a binary tree, return the number of uni-value subtrees. A uni-value subtree means all nodes of the subtree have the same value.

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 count_unival_subtrees(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    let mut count = 0;
    Self::is_unival(&root, &mut count);
    count
  }

  fn is_unival(node: &Option<Rc<RefCell<TreeNode>>>, count: &mut i32) -> bool {
    match node {
      None => true,
      Some(n) => {
        let n = n.borrow();
        let left_uni = Self::is_unival(&n.left, count);
        let right_uni = Self::is_unival(&n.right, count);
        if !left_uni || !right_uni {
          return false;
        }
        if let Some(ref l) = n.left {
          if l.borrow().val != n.val { return false; }
        }
        if let Some(ref r) = n.right {
          if r.borrow().val != n.val { return false; }
        }
        *count += 1;
        true
      }
    }
  }
}