Count nodes equal to sum of descendants

Tree Depth-First Search Binary Tree

77.4% acceptance

Mar 31, 2026

184

Given the root of a binary tree, return the number of nodes where the value of the node is equal to the sum of the values of its descendants. A descendant of a node x is any node that is on the path from node x to some leaf node. The sum is considered to be 0 if the node has no descendants.

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 equal_to_descendants(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    let mut count = 0;
    Self::dfs(&root, &mut count);
    count
  }
  
  fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, count: &mut i32) -> i64 {
    if let Some(n) = node {
      let n = n.borrow();
      let left_sum = Self::dfs(&n.left, count);
      let right_sum = Self::dfs(&n.right, count);
      let desc_sum = left_sum + right_sum;
      if desc_sum == n.val as i64 {
        *count += 1;
      }
      desc_sum + n.val as i64
    } else {
      0
    }
  }
}