LeetCode 337. House Robber III

[Woodyiiiiiii]

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:

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

     3
    / \
   2   3
    \   \ 
     3   1

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

Example 2:

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

     3
    / \
   4   5
  / \   \ 
 1   3   1

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

---

这道题从二叉树的根结点开始，求经过的路径的最大和，要求相邻节点不能计算。这是Shopee一面的题目，我竟然没想出来，好好反思

首先想到对每个节点，要查询，要么取自己本身节点加上不相邻的最多四条相隔孙子节点，要么取与自己本身节点相邻的最多两个儿子节点，最后得到最大值，那么最原始的方法就是递归！！！

class Solution {
    public int rob(TreeNode root) {
        if (root == null)
            return 0;
        int ll = root.left != null ? rob(root.left.left) : 0;
        int lr = root.left != null ? rob(root.left.right) : 0;
        int rr = root.right != null ? rob(root.right.right) : 0;
        int rl = root.right != null ? rob(root.right.left) : 0;
        int var = root.val + ll + lr + rr + rl;
        return Math.max(rob(root.left) + rob(root.right), var);
    }
}

再尝试优化，使用动态规划中的记忆数组(存储)，存储每个节点的最大路径，然后返回，无需重复递归计算。

class Solution {
    Map<TreeNode, Integer> memo = new HashMap<>();
    public int rob(TreeNode root) {
        if (root == null)
            return 0;
        if (memo.containsKey(root))
            return memo.get(root);
        int ll = root.left != null ? rob(root.left.left) : 0;
        int lr = root.left != null ? rob(root.left.right) : 0;
        int rr = root.right != null ? rob(root.right.right) : 0;
        int rl = root.right != null ? rob(root.right.left) : 0;
        int var = root.val + ll + lr + rr + rl;
        memo.put(root, Math.max(rob(root.left) + rob(root.right), var));
        return memo.get(root);
    }
}

---

参考资料：

• https://leetcode.com/problems/house-robber-iii/
• https://leetcode.com/problems/house-robber-iii/discuss/664863/very-simple-and-easy-to-understand-solutuon
• [LeetCode] 337. House Robber III grandyang/leetcode#337