Monitor binary trees

The title

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

prompt

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

Answer key

Dynamic programming + recursion

Each camera head can monitor its parent, itself, and its immediate children. Define three states

  • Status 1: The root node has cameras, and the minimum number of cameras to be covered on all nodes
  • State 2: minimum number of cameras covered by all nodes
  • State 3: the minimum number of cameras covered by the left and right child nodes

State transition equation:

  • Status 1: State 3 of the left child node + state 3 + 1 of the right child node
  • Status 2: the minimum value of status 1, left child node status 3 + right child node status 1, right child node status 3 + left child node status 1
  • State 3: State 1: minimum of state 2 of the left child node and state 2 of the right child node

Edit the code as follows:

The complete code

var minCameraCover = function(root) {
    return dfs(root)[1]
    function dfs(node){
        if(node === null) return [Infinity.0.0];

        const [la,lb,lc] = dfs(node.left)
        const [ra,rb,rc] = dfs(node.right)

        // A indicates the minimum value that can be monitored on the root node
        const a =  lc + rc + 1 ;
        // b indicates that all nodes can be monitored
        const b = Math.min(a,ra + lb,la + rb )

        // c overwrites monitoring of all child nodes
        const c = Math.min(a,lb + rb)
        return [a,b,c]

    }
  
}
Copy the code

conclusion

The author level is limited, if there is insufficient welcome to correct; Any comments and suggestions are welcome in the comments section