Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

After robbing a street and a circle of houses, the thieves found a new area to burglarize. 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.

Related Topics:

  • 198
  • 213. II

The three problems can be summarized as: straight line robbery, ring robbery, binary tree robbery.

Answer:

Same as the previous two problems, start with two states of a single node. For any node:

  1. When a node is selected, its left and right byte points cannot be selected.
  2. If a node is not selected, its left and right byte points may or may not be selected.

Since the selection of each node is affected by both child nodes, we first calculate the results of the two states of the byte point and then the results of the two states of the parent node. Therefore, the order traversal of the binary tree can be carried out through depth-first, that is, the results of the two states of the left and right nodes are calculated first, and then the results of the two states of the parent node are calculated according to this.

Because each node has both selected and unselected results, the result data for each node is represented by an array of length 2, with the first element representing the unselected result and the second element representing the selected result.

This is a dynamic programming of a tree structure. Since depth-first traversal is required, the null state can be used as the initial state, which is [0, 0].

For any non-empty node, assuming its node state is array left[], its right node state is right[], and its own state is curr[], then:

  • curr[0] = max(left[0], left[1]) + max(right[0], right[1])
  • Curr [1] = left[0] + right[0] + current node value

The end result is the greater of the two numbers in the state with the node.

In addition, since the whole process is completed in the sequential traversal, and the state of each node is only related to its left and right nodes, there is no need to save the state of each step.

Final code:

class Solution {
    public int rob(TreeNode root) {
        int[] result = dfs(root);
        return Math.max(result[0], result[1]);
    }
    public int[] dfs(TreeNode curr) {
        if (curr == null) {
            return new int[2];
        }
        int[] left = dfs(curr.left);
        int[] right = dfs(curr.right);
        return new int[]{left[1] + right[1] + curr.val, Math.max(left[0], left[1]) + Math.max(right[0], right[1])}; }}Copy the code