Delete tree nodes

Array Tree Depth-First Search Breadth-First Search

61.7% acceptance

Mar 31, 2026

235

No description available.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn delete_tree_nodes(nodes: i32, parent: Vec<i32>, value: Vec<i32>) -> i32 {
    let n = nodes as usize;
    let mut children = vec![vec![]; n];
    for i in 1..n {
      children[parent[i] as usize].push(i);
    }
    // Post-order: returns (subtree_sum, count_of_remaining_nodes)
    fn dfs(node: usize, children: &Vec<Vec<usize>>, value: &Vec<i32>) -> (i64, i32) {
      let mut sum = value[node] as i64;
      let mut count = 1;
      for &child in &children[node] {
        let (cs, cc) = dfs(child, children, value);
        sum += cs;
        count += cc;
      }
      if sum == 0 { (0, 0) } else { (sum, count) }
    }
    let (_, count) = dfs(0, &children, &value);
    count
  }
}