House Robber III

问题描述

House Robber III
一颗二叉树有n个节点，每个节点都有一个权值，现在要求你从中选出任意个节点，使得加起来的权值最大。同时满足一个约束：不存在任意两个节点有相邻边连接（即有父子关系的节点不可以同时选，儿子和爷爷可以，兄弟节点可以）。

算法思路

从根节点出发，为了获得最大的权值，需要考虑两种情况：

1. 考虑根节点；
2. 不考虑根节点，同时累加根节点的左右节点；

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