[LeetCode] 337. House Robber III

轉自LeetCode

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

     3
    / \
   2   3
    \   \ 
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

     3
    / \
   4   5
  / \   \ 
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

<Solution>

198. House Robber 的衍生題，資料結構變成 binary tree

想法如下

• 每個節點都有選與不選兩種狀況。如果該節點被選，則它的兩個子節點就不能被選；反之，他兩個子節點可以被選

• 樹的資料結構，加上有選與不選的狀況，使用 recursive 來解

• 回傳一個 int[]，第一個位置放包含該節點的最佳解，第二個位置放不包含該節點的最佳解

code 如下

Java(參考解法)

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public int rob(TreeNode root) {
	int[] ans = robHouse(root);
	//>> index 0: include root
	//>> index 1: exclude root
	return Math.max(ans[0], ans[1]);
	}
	private int[] robHouse(TreeNode root) {
	if(root == null) {
	return new int[2];
	}
	int[] left = robHouse(root.left);
	int[] right = robHouse(root.right);
	int[] res = new int[2];
	//>> include root. Both left and right child cannot be included
	res[0] = root.val + left[1] + right[1];
	//>> exclude root
	res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
	return res;
	}
	}

view raw rob3.java hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	fun rob(root: TreeNode?): Int {
	val ans = dfs(root)
	return Math.max(ans[0], ans[1])
	}
	fun dfs(node: TreeNode?): IntArray {
	return if(node == null) {
	IntArray(2) {0}
	} else {
	val left = dfs(node!!.left)
	val right = dfs(node!!.right)
	val result = IntArray(2)
	//>> select root
	result[0] = node!!.`val` + left[1] + right[1]
	//>> select child
	result[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1])
	return result
	}
	}
	}

view raw house_robber_III.kt hosted with ❤ by GitHub