问题描述
House Robber III
一颗二叉树有n个节点，每个节点都有一个权值，现在要求你从中选出任意个节点，使得加起来的权值最大。同时满足一个约束：不存在任意两个节点有相邻边连接（即有父子关系的节点不可以同时选，儿子和爷爷可以，兄弟节点可以）。
算法思路
从根节点出发，为了获得最大的权值，需要考虑两种情况：
- 考虑根节点；
- 不考虑根节点，同时累加根节点的左右节点；
rob(root)函数的定义为：返回从root节点开始的能够抢到的最大权值
第一种情况：
在左孩子存在的情况下：
value1 += rob(root.left.left) + rob(root.left.right);
在右孩子存在的情况下：
value1 += rob(root.right.left) + rob(root.right.right);
第二种情况：
value2 = rob(root.left) + rob(root.right);
最大的权值即为：Math.max(value1 + root.val, value2);
由此可得，递推方程为：
rob(root) = Math.max(value1 + root.val, rob(root.left) + rob(root.right));
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) {
return robSub(root, new HashMap<>());
}
private int robSub(TreeNode root, Map<TreeNode, Integer> map) {
if (root == null) return 0;
if (map.containsKey(root)) return map.get(root);
int val = 0;
if (root.left != null) {
val += robSub(root.left.left, map) + robSub(root.left.right, map);
}
if (root.right != null) {
val += robSub(root.right.left, map) + robSub(root.right.right, map);
}
val = Math.max(val + root.val, robSub(root.left, map) + robSub(root.right, map));
map.put(root, val);
return val;
}
}
相关问题
如果不是一颗二叉树，而是一颗普通的树，如何求解？
此时需要用一个数组记录哪些节点被访问过了，同时两个if条件需要更改为for循环，用于访问邻接的未访问过的节点。
参考文献
https://discuss.leetcode.com/topic/39834/step-by-step-tackling-of-the-problem
