https://leetcode.cn/problems/house-robber-iii/
package 代码随想录.动态规划;
import 代码随想录.树.TreeNode;
public class _337打家劫舍III_直接遍历 {
/**
*
* @param root
* @return
*/
public int rob(TreeNode root) {
//树形邻居
//跳着遍历邻居
if (root == null){
return 0;
}
int money = root.val;
if (root.left != null){
money += (rob(root.left.left) + rob(root.left.right));
}
if (root.right != null){
money += (rob(root.right.left) + rob(root.right.right));
}
return Math.max(money,rob(root.left) + rob(root.right));
}
}
package 代码随想录.动态规划;
import 代码随想录.树.TreeNode;
import java.util.HashMap;
import java.util.Map;
public class _337打家劫舍III_递归遍历 {
/**
*
* @param root
* @return
*/
public int rob(TreeNode root) {
Map<TreeNode,Integer> memo = new HashMap<TreeNode,Integer>();
return robAction(root,memo);
}
/**
*
* @param root
* @param memo
* @return
*/
private int robAction(TreeNode root, Map<TreeNode, Integer> memo) {
if (root == null){
return 0;
}
if (memo.containsKey(root)){
return memo.get(root);
}
int money = root.val;
if (root.left != null){
money += robAction(root.left.left ,memo) + robAction(root.left.right,memo);
}
if (root.right != null){
money += robAction(root.right.left,memo) + robAction(root.right.right,memo);
}
int res = Math.max(money,robAction(root.left,memo) + robAction(root.right,memo));
memo.put(root,res);
return res;
}
}
package 代码随想录.动态规划;
import 代码随想录.树.TreeNode;
public class _337打家劫舍III_dp {
/**
* // 3.状态标记递归
* // 执行用时:0 ms , 在所有 Java 提交中击败了 100% 的用户
* // 不偷:Max(左孩子不偷,左孩子偷) + Max(右孩子不偷,右孩子偷)
* // root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) +
* // Math.max(rob(root.right)[0], rob(root.right)[1])
* // 偷:左孩子不偷+ 右孩子不偷 + 当前节点偷
* // root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
* @param root
* @return
*/
public int rob(TreeNode root) {
int result [] = rotAction(root);
return Math.max(result[0],result[1]);
}
/**
*
* @param root
* @return
*/
private int[] rotAction(TreeNode root) {
int result [] = new int[2];
if (root == null) {
return result;
}
int [] left = rotAction(root.left);
int [] right = rotAction(root.right);
result[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
result[1] = root.val + left[0] + right[0];
return result;
}
}