Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

Monitor binary trees

Given a binary tree, we install cameras on the nodes of the tree.

Each photography header on a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras required for all nodes of the monitoring tree.

 

Example 1:

Input: [0,0,null,0,0] output: 1 description: as shown in the figure, one camera is sufficient to monitor all nodes.Copy the code

Example 2:

Input: [0, 0, null, 0, null, 0, null, null, 0] output: 2: you need at least two cameras to monitor all the nodes of the tree. The image above shows one of the effective locations for the camera.Copy the code

Tip:

  1. The range of nodes in a given tree is[1, 1000].
  2. Each node has a value of 0.

Train of thought

  1. To monitor every node, we monitor either the current node or a child node of the current node.
  2. The problem is to find the minimum number of cameras, so we can use dynamic programming to ensure that our solution is optimal when we reach each node at each level, so that when we reach the last node at the last level, our answer is naturally the best answer;
  3. Dynamic programming involves state transition equations. For example, if we want to listen on the root node of a tree structure as follows, we need to listen on the root node or on one of the left and right child nodes;

  1. If the left and right child nodes have children, they can be divided into several cases: Camera is placed in one place, and then calculate the 4-5-6 three nodes need to spend how many cameras, or put a camera in 2 place, and then calculate the 3-5-6 the three nodes need to spend how many cameras, or cameras is put in 3, and then calculate how many cameras will take 2-4, this is the only three is not the fourth, So we can minimize these three cases;

  1. We can judge whether the current node has left and right child nodes. If not, we will not calculate and solve the current problem recursively. As long as we ensure that every step is optimal, the answer will naturally be the minimum value.

implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number}* /
var minCameraCover = function(root, isMust = false, isCover = false) {
    if(! root) {return 0;
    }

    // Classification is discussed according to whether there are child nodes
    if(! root.left && ! root.right) {// There is no child node, indicating that the current monitoring is complete
        // Add a camera to monitor the current node
        return isCover ? 0 : 1;
    } else if(! root.left || ! root.right) {// If necessary
        if (isMust) {
            return minCameraCover(root.left || root.right, false.true) + 1;
        }

        // If already monitored
        if (isCover) {
            return Math.min(
                minCameraCover(root.left || root.right, false.false),
                minCameraCover(root.left || root.right, false.true) + 1
            );
        }

        // If there is only one child, this round is not monitored then child monitoring is required
        return Math.min(
            minCameraCover(root.left || root.right, false.true) + 1,
            minCameraCover(root.left || root.right, true.false),)}else {
        // If necessary
        if (isMust) {
            return minCameraCover(root.left, false.true) + 
                minCameraCover(root.right, false.true) + 1;
        }

        // If already monitored
        if (isCover) {
            return Math.min(minCameraCover(root.left, false.false) + 
                    minCameraCover(root.right, false.false),
                    minCameraCover(root.left, false.true) + 
                    minCameraCover(root.right, false.true) + 1);
        }


        // If there are two child nodes, choose one of them, or monitor the root node directly
        return Math.min( ... [ minCameraCover(root.left,false.true) + 
                minCameraCover(root.right, false.true) + 1,
                minCameraCover(root.left, true.false) +
                minCameraCover(root.right, false.false),
                minCameraCover(root.left, false.false) + 
                minCameraCover(root.right, true.false),])}};Copy the code

rollover

After finishing my thinking, I typed out the code, only to find that I had timed out. Awkward, and a lot of redundant code, so let’s cut it down and see if it works.

To streamline the code

/ * * *@param {TreeNode} root
 * @return {number}* /
var minCameraCover = function(root, isMust = false, isCover = false) {
    if(! root) {return 0;
    }

    // Classification is discussed according to whether there are child nodes
    if(! root.left && ! root.right) {// There is no child node, indicating that the current monitoring is complete
        // Add a camera to monitor the current node
        return isCover ? 0 : 1;
    } else {
        constisLose = ! root.left || ! root.right;// If necessary
        if (isMust) {
            return minCameraCover(root.left, false.true) + 
                minCameraCover(root.right, false.true) + 1;
        }

        // If already monitored
        if (isCover) {
            return  Math.min(minCameraCover(root.left, false.false) + 
                    minCameraCover(root.right, false.false),
                    minCameraCover(root.left, false.true) + 
                    minCameraCover(root.right, false.true) + 1);
        }


        // If there is only one child, this round is not monitored then child monitoring is required
        // If there are two child nodes, choose one of them, or monitor the root node directly
        return isLose ? 
            Math.min(
                minCameraCover(root.left || root.right, false.true) + 1,
                minCameraCover(root.left || root.right, true.false)) :Math.min( ... [ minCameraCover(root.left,false.true) + 
                minCameraCover(root.right, false.true) + 1,
                minCameraCover(root.left, true.false) +
                minCameraCover(root.right, false.false),
                minCameraCover(root.left, false.false) + 
                minCameraCover(root.right, true.false),])}};Copy the code

Rollover again

This version of the code and a lot of simplification, readability is barely acceptable, but still timeout, which means that we directly recurse is not going to work, so we need to find a pattern. In fact, in the top-down process, we need to compare whether each node is optimal, which means that we need to go through all possible paths from top to bottom every time, which is the lowest performance. So let’s think about it the other way, bottom up, same idea.

Set sail again

  1. If the node does not have children, then you can hang a camera on your own body, you can also hang a camera on the parent node, we use greedy thinking, want to get the least camera, then can hang a camera on the parent node do not hang on the child node;
  2. We can use three numbers0-1-2To identify the monitoring situation of each node,0Indicates that the current node is not monitored0If it doesn’t have any children, you can put a camera on its parent node.
  3. For example, every time we only need to judge whether there are unmonitored child nodes on the current node, and if there are, we need to mount cameras on the current node. If there are cameras, we need to count the number and add the number of cameras on the node.
  4. If the current node has a camera attached, then the value of the current node is used2The parent node can determine whether there is a camera in the child node. If so, the parent node can use the camera1To indicate that it has been monitored, but before you do that, you have to make sure that the other node is monitored, that the other child node cannot be0;
  5. Not at the child node0If the current node is1Do not operate;
  6. Finally, the optimal solution of each node can be converted to the optimal solution of the left node + the optimal solution of the right node, plus one if the current need to monitor.

The final code

/ * * *@param {TreeNode} root
 * @return {number}* /
var minCameraCover = function(root) {
    let result = dfs(root);

    // Determine whether the current camera needs monitoring after recursion
    if (root && root.val === 0) {
        result++
    }

    return result;
};

// Walk through the binary tree to find whether the child node has a camera
function dfs(node) {
    if(! node) {return 0;
    }

    // First visit the left and right child nodes to determine whether they are monitored
    const left = dfs(node.left);
    const right = dfs(node.right);

    let result = left + right;

    // Specify the three states of the camera
    // 0 indicates that the system is not monitored
    // 1 means monitored
    // 2 indicates that the camera is installed

    // If the child node is not monitored, the parent node is out
    if (node.left && node.left.val === 0 || node.right && node.right.val === 0) {
        node.val = 2;
        result++;
    } else  // If the child node is installed with a camera, the parent node can also monitor the child node
    if (node.left && node.left.val === 2 || node.right && node.right.val === 2) {
        node.val = 1;
    }

    return result;
}
Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.