This is the 14th day of my participation in Gwen Challenge

The tree DP

Tree DP, as the name suggests, is the kind of problem that does DP on a binary tree, or on a multi-fork tree. Although it looks like a binary tree problem, it’s essentially a DP problem.

Example: binary tree heist

The title

After robbing a street and a ring of houses, the thieves found a new area to burgle. There is only one entrance to this area, which we call the root. In addition to the root, each house has one and only one parent house attached to it. After some sleuthing, the clever thief realized that “all the houses in this place are arranged like a binary tree.” If two directly connected houses are robbed on the same night, the house will automatically alarm the police. Calculate the maximum amount of money a thief could steal in one night without setting off the alarm.

Input: [3, 2, 3, null, 3, null, 1)

Output: 7

Explanation: Maximum amount of money a thief can steal in one night = 3 + 3 + 1 = 7.

Analysis of the

When we see the word “highest”, we should think of using the DP method to try it out. First, we do what we do best. Last.

1. Last step

If a thief always steals the subtree first, then the last step must be the root of the binary tree. There are only two possibilities for the root:

  • Grab the root node
  • Don’t grab the root

Now that we have these two possibilities, we just have to maximize both of them.

2. The problem of child

If we further expand the two cases of the root node, we can find:

Grab the root, this time can not grab the left and right two subtree root;

You don’t grab the root, so you can grab the root of two subtrees, or you can skip the root of two subtrees.

We found that the root node needs to get two pieces of information: “Maximum benefit from taking root, maximum benefit from not taking root”, and the left and right subtrees also need these two pieces of information.

Then we can define a function f(x) to describe the requirements of the last step and the requirements of the sub-problem:

F (x) = < maximum gain from robbing X, maximum gain from not robbing X >

For the convenience of later description, we will use the following abbreviations to represent the information of the above two dimensions:

F (x) = < rob, don’t rob > = < take x maximum gain, don’t rob the biggest benefit of x > Max (f (x) = Max < f (x). Grab,f(x). Not grab >

3. Recursive relationships

At this point, we can write recursion based on the last step and subproblem:

F (root). Grab = root.val + f(root.left). Do not rob + F (root.right). Do not rob F (root). = Max (f(root.left)) + Max (f(root.right)))

4. Representation of f(x)

So let’s first look at the return value of f of x, because there are only two return values. This is easier to handle, for Python you can return two values directly, and for Java you can return an array of long[2] directly.

And then let’s look at the representation of f of x. When we start at the bottom and work our way up, there should only be two adjacent floors that depend on each other.

Further information between layers does not need to be retained, so the f(x) function does not need a hash or array to record [x] information. This is equivalent to using DFS directly without memorizing DFS.

5. Initial conditions and boundaries

When an empty tree is encountered, simply return long[2] = {0, 0}, that is, return 0.

6. Compute the order

Here we use the first tree subtree, so we need to use the order after traversal.

The complete code

At this point, we can write the following code (resolved in comments) :

class Solution {
    // Return a pair
    // ans[0] : grab the current root
    // ans[1] indicates that the current node cannot be robbed
    private long[] postOrder(TreeNode root) {
        if (root == null) {
            return new long[] { 0.0 };
        }
        long[] l = postOrder(root.left);
        long[] r = postOrder(root.right);
        // If you want to grab the current node
        long get = root.val;
        // Then the two children must not be robbed
        get += l[1] + r[1];
        // If you do not grab the current node
        long skip = 0;
        // Then the two children may or may not be robbed
        skip += Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new long[] { get, skip };
    }
    public int rob(TreeNode root) {
        long[] ans = postOrder(root);
        return (int) Math.max(ans[0], ans[1]); }}Copy the code

Complexity analysis: Time complexity, which is essentially a post-order traversal, so O(N). Counting the space occupied by the stack, the space complexity is O(H), where H represents the height of the tree.

summary

In the end, we can sum up the following points:

  • DP analysis
  • After the sequence traversal

In addition, when processing the final return value of this problem, the return value of the sequential traversal does not directly return the answer we want, but carries the information of the subtree, and then leaves it to the root node to integrate this part of information.