preface

Today’s topic is a problem that combines greed and dynamic programming in binary trees.

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.Copy the code

The title and dismantling

The core of this topic is how to cover the entire tree with minimal monitoring. In the optimization of the processing method, usually use dynamic programming and greedy to deal with, today also use these two ways to solve.

Dynamic programming

The idea of using dynamic programming is mainly to pay attention to state transition. In the traditional single-line dynamic programming, state transition is relatively easy to achieve, but in the binary tree, state transition becomes a little cumbersome, we will analyze step by step.

State definition

In fact, the idea of dynamic programming is to consider the overall scope, take the coverage of the whole tree as a basic state, and then transfer the state to the parent node. So, how many states does a tree have? It’s a little hard to visualize, but let’s put ourselves in the position of a node, and think about what state that node depends on in the subtree.

  • The left and right subtrees are overwritten, but the root nodes of the left and right subtrees are not monitored.
  • The left and right subtrees are covered, and at least one of the root nodes of the left and right subtrees is monitored.
  • The children of the left and right subtrees are overwritten, but at least one of the root nodes of the left and right subtrees is not overwritten.

1. In the first state, the left and right subtrees are all monitored, but the root nodes of the left and right subtrees are not monitored, so the current node should consider whether to monitor (see if the parent node can monitor). 2. In the second state, the left and right subtrees are all covered, and a root node of a tree has been monitored, which can cover the current node. Therefore, this node can not be added. 3. In the third state, all the child nodes of the left and right subtrees are covered, but the root node of at least one subtree is not covered, so the current node must be monitored, otherwise some nodes will not be covered.

So, to tidy up, a node has three choices whether to add monitoring, must add, need to add its own or parent node, can not add, we map these three states to the tree itself, tidy up three states:

1. Status A: A tree is monitored and the root node is monitored. (The parent node may not be added)

2. State B: A tree is fully monitored. The root node can be monitored or not. (Father’s Day plus or not depends on the situation)

3. State C: A tree is covered by monitoring except for the root node, which may or may not be covered. (Parent node must be added)

Draw three pictures to illustrate

State a

State b

The state c

The above is the tree display form under the three states, because the monitoring of each node depends on the corresponding monitoring quantity of the three states of the sub-tree, so we maintain the storage of the three states for each node, and then transfer the state to the parent node in the recursive process.

Next, we use Ca,Cb and Cc to represent the number of monitoring required in different states. It can be seen from the example figure that Ca>=Cb>=Cc what we actually need, or what we want to obtain, is the number of monitoring in state B. State A has a redundant monitoring, and state C may have missing root node coverage.

So, the first step of dynamic programming, we have completed, with an int[] to maintain the number of monitoring corresponding to the three states.

Next, state transitions.

State transition

Once the states are defined, state transitions are relatively easy. When traversing each node, calculate the values of Ca, Cb and Cc respectively, assuming that the state array of the child node is int[] left and the state array of the right node is int[] right. So there is.

  • Ca = left[2]+right[2] + 1; // Insert the current node into a monitor without checking whether the root node is monitored.
  • Cb = math.min (Ca, math.min (left[0]+right[1],left[1]+right[0]))
  • Cc = Math.min(Cb,left[1]+right[2])

So we’re done with the state transition, and with the state definition and the state transition, our code is out.

Dynamic programming code

class Solution { public int minCameraCover(TreeNode root) { int[] res = dfsOne(root); return res[1]; } int[] dfsOne(TreeNode node) { if (node == null) return new int[]{Integer.MAX_VALUE / 2, 0, 0}; int[] array = new int[3]; int[] leftArray = dfsOne(node.left); int[] rightArray = dfsOne(node.right); int a = leftArray[2] + rightArray[2] + 1; int b = Math.min(a, Math.min(leftArray[1] + rightArray[0], leftArray[0] + rightArray[1])); int c = Math.min(b, leftArray[1] + rightArray[1]); array[0] = a; array[1] = b; array[2] = c; return array; }}Copy the code

The divider

greedy

The core of the greedy algorithm, in fact, one word, greed.

If there’s one word, it’s lazy.

Compared with dynamic programming, which is triggered from the standpoint of the whole tree, greedy is completely from the perspective of the node itself. Never monitor anything unless you have to, which is the heart of greedy algorithms, and to keep in mind as you comb through your logic.

So what we need to do is look at the mental history of a node as we traverse it.

  • The root of the left and right subtrees is monitored, so that’s great, don’t worry about anything, tell the boss it’s overwritten, don’t worry about me.
  • If the child node is monitored, but the root node of the left and right subtree is not monitored, then what to do?
  • If the child node is not covered by monitoring, then the current node must be added, no one can cover the child node, tell the boss I added monitoring, invite credit.

These three states are different from dynamic programming. In greedy algorithm, the current node only reports its state to the superior and does not need to manage the state of the whole tree.

Let’s also define the state of this node.

  • In state 1, the current node has been overwritten
  • In state 2, the current node is not overwritten
  • In state 3, the current node is monitored

Now that we have this idea, and we have the criteria, let’s look at greedy code

Greedy code

class Solution { public int minCameraCover(TreeNode root) { int resTwo = dfsTwo(root); if (resTwo == 2) { totalCount++; } return totalCount; } private int totalCount = 0; Int dfsTwo(TreeNode node) {// State 1, the current node is overwritten // State 2, the current node is not overwritten // State 3, the current node has a camera if (node == null) {// Empty node is overwritten by default return 1; } int left = dfsTwo(node.left); int right = dfsTwo(node.right); / / her two child nodes one party has not been covered, so they don't add not line, in the current node and a monitoring the if (left = = 2 | | right = = 2) {totalCount++; return 3; } / / two child nodes have a monitoring, the current node has been covered, there is no need to add the monitor. The if (left = = 3 | | right = = 3) {return 1; } left == 1 right == 1 left == 1 left == 1 right == 1 }Copy the code

conclusion

Today’s problem is a difficult one, so I sorted out the solution of the official problem and the solution of other great gods, summarized the two ideas to do, and also showed respect for the difficult problem.

In fact, as you can see, there is not much code in this topic. If you remove the comments, there are only a few lines. However, it is a bit complicated to think about the entry point and idea of the problem, which needs to be carefully considered.

In addition, both dynamic planning and greed are essentially the upward transmission of a state. However, dynamic planning is based on describing the whole tree, while greed describes the node itself. Dynamic planning saves a lot of state judgment, and greed does not have so much data redundancy.

Use whichever you like

This article is participating in the “Nuggets 2021 Spring recruiting campaign. Click here to view