LeetCode 337. House robbing III

My LeetCode: https://leetcode-cn.com/u/ituring/

My LeetCode source code [GitHub]: https://github.com/izhoujie/Algorithmcii

LeetCode 337. House robbing III

subject

After robbing a street and a circle of houses last time, thieves found a new area where they could steal. This area has only one entrance, which we call "root". In addition to the "root", each house has and only has a "parent" house connected to it. After some reconnaissance, 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.

Calculate the maximum amount that a thief can steal overnight without triggering an alarm.
Example 1:

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

     3
    / \
   2   3
    \   \ 
     3   1

Output: 7 
Explanation: the maximum amount that a thief can steal in one night = 3 + 3 + 1 = 7

Example 2:

Input: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

Output: 9
 Explanation: the maximum amount that a thief can steal in one night = 4 + 5 = 9

Source: LeetCode
Links: https://leetcode-cn.com/problems/house-robber-iii
Copyright belongs to the network. For commercial reprint, please contact the official authorization. For non-commercial reprint, please indicate the source.

Solving problems

You must first understand the meaning of the topic: you can't rob any two connected nodes, or for a node, you can either rob the current node and its left and right nodes' children (grandchildren), or rob its left and right direct children without robbing the current node;

Train of thought 1 - based on the above questions, use dp + recursion method to solve;

The idea is to use nodes to record intermediate values:

  1. The null node returns a value of 0;
  2. The maximum values of left and right nodes are calculated recursively;
  3. When going to the node of the previous layer, the following maximum values are taken for calculation:
    • Grab the sum of the maximum values of the current node and its left and right nodes (grandchildren);
    • Do not grab the current node, only grab the sum of the maximum values of the left and right child nodes (direct node);

Idea 2 - same as 1, but using array to record intermediate data;

Array index 0 represents the maximum value when the current node is not robbed, and 1 represents the maximum value when the current node is robbed. Other process ideas are the same as 1;

Algorithm source code example

package leetcode;

/**
 * @author ZhouJie
 * @date 2020 9:07:56 PM, March 24, 2015 
 * @Description: 337. House robbing III
 * 
 *
 */
public class LeetCode_0337 {

}

// Definition for a binary tree node.
class TreeNode_0337 {
	int val;
	TreeNode_0337 left;
	TreeNode_0337 right;

	TreeNode_0337(int x) {
		val = x;
	}
}

class Solution_0337 {
	/**
	 * @author: ZhouJie
	 * @date: 2020 1:48:54 p.m., March 31, 2015 
	 * @param: @param root
	 * @param: @return
	 * @return: int
	 * @Description: 1-For a node, there are two possible maximum values that can be stolen at present:
	 * 				- Steal the sum of the maximum values of the current node and its left and right nodes' children (the sum of the maximum values of the four grandchildren);
	 * 				- Do not steal the current node, and steal the sum of the maximum values of the left and right child nodes;
	 * 				- Children and grandchildren are recursive problems;
	 *
	 */
	public int rob_1(TreeNode_0337 root) {
		TreeNode_0337 left = new TreeNode_0337(0);
		TreeNode_0337 right = new TreeNode_0337(0);
		return robMax_1(root, left, right);
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020 1:56:46 PM, March 31, 2016 
	 * @param: @param root
	 * @param: @param left
	 * @param: @param right
	 * @param: @return
	 * @return: int
	 * @Description: 1-dp+Recursion (node record value);
	 *
	 */
	private int robMax_1(TreeNode_0337 root, TreeNode_0337 left, TreeNode_0337 right) {
		if (root == null) {
			return 0;
		} else {
			// Four grandchildren
			TreeNode_0337 ll, lr, rl, rr;
			ll = new TreeNode_0337(0);
			lr = new TreeNode_0337(0);
			rl = new TreeNode_0337(0);
			rr = new TreeNode_0337(0);
			// Maximum value of left and right child nodes
			left.val = robMax_1(root.left, ll, lr);
			right.val = robMax_1(root.right, rl, rr);
			return Math.max(root.val + ll.val + lr.val + rl.val + rr.val, left.val + right.val);
		}
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020 1:57:30 p.m., March 31, 2015 
	 * @param: @param root
	 * @param: @return
	 * @return: int
	 * @Description: 2-The difference with 1 is only that it uses array to save the intermediate value;
	 *
	 */
	public int rob_2(TreeNode_0337 root) {
		int[] rob = robMax_2(root);
		return Math.max(rob[0], rob[1]);
	}

	private int[] robMax_2(TreeNode_0337 root) {
		if (root == null) {
			// Empty node returns empty array for upper layer calculation
			return new int[2];
		}
		// Final rob array of left and right child nodes
		int[] left = robMax_2(root.left);
		int[] right = robMax_2(root.right);
		int[] robbing = new int[2];
		// Finally, make a choice and do not rob the current root node (that is, the left and right child nodes can rob or not rob), then select the maximum value of rob or not rob from the left and right child nodes;
		robbing[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
		// If you want to grab the current heel node, you can only select the value when the left and right child nodes do not grab and add the value of the current root node
		robbing[1] = left[0] + right[0] + root.val;
		return robbing;
	}
}

Tags: Java github network

Posted on Thu, 02 Apr 2020 12:46:42 -0700 by chandan_tiwari