Leetcode daily question (968. binary tree cameras)

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.

Example 1:

Input: root = [0,0,null,0,0]
Output: 1

Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2

Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• Node.val == 0

---

Assign a number to each node in the tree , This is not a problem , left = curr * 2 + 1, right = curr * 2 + 2, hypothesis dp[i][is_covered][need_place] It represents the first in the tree i Whether nodes are covered by cameras (is_covered) And is it mandatory to install a camera on the node (need_place) In the case of i The minimum number of cameras required for the subtree of the root node . In this way, we can divide the situation into three kinds , One is the mandatory installation of cameras need_place == true, In this way, its left and right child nodes will be covered ( We are top-down , Regardless of parent node ), So the result is dp[i*2+1][true][false] + dp[i*2+2][true][false] + 1, If forced installation is not required , Let's see whether it covers (is_covered), If the current node has been overwritten , We can place cameras on the current node , That's the same as the situation mentioned above , dp[i*2+1][true][false] + dp[i*2+2][true][false] + 1, You can also not place , Because the current node has been overwritten , So even if we don't place cameras on the current node , There is no need to force the placement of cameras in that sub node , So the result is dp[i*2+1][false][false] + dp[i*2+2][false][false], The smaller of these two cases returns . The last is that there is neither mandatory placement nor coverage , Then we can place the camera on the current node ( ditto ), You can also force cameras to be placed on the left or right child nodes , dp[i*2+1][false][true] perhaps dp[i*2+2][false][true], Take the minimum value in these three cases

---

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;
impl Solution {
    
    fn dp(root: &Option<Rc<RefCell<TreeNode>>>, val: i32, is_covered: bool, need_place: bool, cache: &mut HashMap<(i32, bool, bool), i32>) -> i32 {
    
        if let Some(node) = root {
    
            if need_place {
    
                let left = if let Some(c) = cache.get(&(val * 2 + 1, true, false)) {
    
                    *c
                } else {
    
                    Solution::dp(&node.borrow().left, val * 2 + 1, true, false, cache)
                };
                let right = if let Some(c) = cache.get(&(val * 2 + 2, true, false)) {
    
                    *c
                } else {
    
                    Solution::dp(&node.borrow().right, val * 2 + 2, true, false, cache)
                };
                cache.insert((val, is_covered, need_place), left + right + 1);
                return left + right + 1;
            }
            if is_covered {
    
                let curr_place = {
    
                    let left = if let Some(c) = cache.get(&(val * 2 + 1, true, false)) {
    
                        *c
                    } else {
    
                        Solution::dp(&node.borrow().left, val * 2 + 1, true, false, cache)
                    };
                    let right = if let Some(c) = cache.get(&(val * 2 + 2, true, false)) {
    
                        *c
                    } else {
    
                        Solution::dp(&node.borrow().right, val * 2 + 2, true, false, cache)
                    };
                    left + right + 1
                };
                let curr_pass = {
    
                    let left = if let Some(c) = cache.get(&(val * 2 + 1, false, false)) {
    
                        *c
                    } else {
    
                        Solution::dp(&node.borrow().left, val * 2 + 1, false, false, cache)
                    };
                    let right = if let Some(c) = cache.get(&(val * 2 + 2, false, false)) {
    
                        *c
                    } else {
    
                        Solution::dp(&node.borrow().right, val * 2 + 2, false, false, cache)
                    };
                    left + right
                };
                let ans = curr_place.min(curr_pass);
                cache.insert((val, is_covered, need_place), ans);
                return ans;
            }
            let curr_place = {
    
                let left = if let Some(c) = cache.get(&(val * 2 + 1, true, false)) {
    
                    *c
                } else {
    
                    Solution::dp(&node.borrow().left, val * 2 + 1, true, false, cache)
                };
                let right = if let Some(c) = cache.get(&(val * 2 + 2, true, false)) {
    
                    *c
                } else {
    
                    Solution::dp(&node.borrow().right, val * 2 + 2, true, false, cache)
                };
                left + right + 1
            };
            let left_place = {
    
                if node.borrow().left.is_none() {
    
                    i32::MAX
                } else {
    
                    let left = if let Some(c) = cache.get(&(val * 2 + 1, false, true)) {
    
                        *c
                    } else {
    
                        Solution::dp(&node.borrow().left, val * 2 + 1, false, true, cache)
                    };
                    let right = if let Some(c) = cache.get(&(val * 2 + 2, false, false)) {
    
                        *c
                    } else {
    
                        Solution::dp(&node.borrow().right, val * 2 + 2, false, false, cache)
                    };
                    left + right
                }
            };
            let right_place = {
    
                if node.borrow().right.is_none() {
    
                    i32::MAX
                } else {
    
                    let left = if let Some(c) = cache.get(&(val * 2 + 1, false, false)) {
    
                        *c
                    } else {
    
                        Solution::dp(&node.borrow().left, val * 2 + 1, false, false, cache)
                    };
                    let right = if let Some(c) = cache.get(&(val * 2 + 2, false, true)) {
    
                        *c
                    } else {
    
                        Solution::dp(&node.borrow().right, val * 2 + 2, false, true, cache)
                    };
                    left + right
                }
            };
            let ans = curr_place.min(left_place).min(right_place);
            cache.insert((val, is_covered, need_place), ans);
            return ans;
        }
        0
    }
    pub fn min_camera_cover(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    
        let mut cache = HashMap::new();
        Solution::dp(&root, 0, false, false, &mut cache)
    }
}