Cousins in binary tree ii

Hash Table Tree Depth-First Search Breadth-First Search Binary Tree

75.8% acceptance

Feb 27, 2026

1221

Given the root of a binary tree, replace the value of each node in the tree with the sum of all its cousins' values. Two nodes of a binary tree are cousins if they have the same depth with different parents. Return the root of the modified tree. Note that the depth of a node is the number of edges in the path from the root node to it.

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 replace_value_in_tree(
    root: Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>,
  ) -> Option<std::rc::Rc<std::cell::RefCell<TreeNode>>> {
    use std::collections::VecDeque;
    type _T = Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>;

    let root = root?;

    // BFS: compute level sums
    // Each element in queue: node
    let mut queue: VecDeque<std::rc::Rc<std::cell::RefCell<TreeNode>>> = VecDeque::new();
    queue.push_back(root.clone());

    // Pass 1: collect level sums
    let mut level_sums: Vec<i32> = Vec::new();
    {
      let mut q = VecDeque::new();
      q.push_back(root.clone());
      while !q.is_empty() {
        let sz = q.len();
        let mut level_sum = 0;
        for _ in 0..sz {
          let node = q.pop_front().unwrap();
          let n = node.borrow();
          level_sum += n.val;
          if let Some(l) = n.left.clone() { q.push_back(l); }
          if let Some(r) = n.right.clone() { q.push_back(r); }
        }
        level_sums.push(level_sum);
      }
    }

    // Pass 2: replace values
    // For each node, its new value = level_sum[depth] - sum of siblings' values (including itself first, then subtract)
    // We process parent -> children: children new value = level_sum[depth+1] - (left_val + right_val)
    root.borrow_mut().val = 0;
    let mut q: VecDeque<(std::rc::Rc<std::cell::RefCell<TreeNode>>, usize)> = VecDeque::new();
    q.push_back((root.clone(), 0));

    while let Some((node, depth)) = q.pop_front() {
      let node_b = node.borrow();
      // Sum of children's values
      let child_sum = node_b.left.as_ref().map_or(0, |l| l.borrow().val)
        + node_b.right.as_ref().map_or(0, |r| r.borrow().val);

      if let Some(l) = node_b.left.clone() {
        let new_val = level_sums[depth + 1] - child_sum;
        l.borrow_mut().val = new_val;
        q.push_back((l, depth + 1));
      }
      if let Some(r) = node_b.right.clone() {
        let new_val = level_sums[depth + 1] - child_sum;
        r.borrow_mut().val = new_val;
        q.push_back((r, depth + 1));
      }
    }

    Some(root)
  }
}