Binary tree cameras

Dynamic Programming Tree Depth-First Search Binary Tree

47.7% acceptance

Feb 27, 2026

5642

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children. Return the minimum number of cameras needed to monitor all nodes of the tree.

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 min_camera_cover(root: Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>) -> i32 {
    let mut cameras = 0i32;
    // Returns: 0=not covered, 1=covered, 2=has camera
    fn dfs(node: &Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>, cameras: &mut i32) -> i32 {
      match node {
        None => 1, // null nodes are considered covered
        Some(n) => {
          let n = n.borrow();
          let l = dfs(&n.left, cameras);
          let r = dfs(&n.right, cameras);
          if l == 0 || r == 0 {
            *cameras += 1;
            2
          } else if l == 2 || r == 2 {
            1
          } else {
            0
          }
        }
      }
    }
    if dfs(&root, &mut cameras) == 0 { cameras += 1; }
    cameras
  }
}