LeetCode题解：打家劫舍III

题目描述

小偷发现一个新的可行窃的地区。这个地区只有一个入口，我们称之为root。
除了root之外，每栋房子有且只有一个“父”房子与之相连。一番侦查之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
给定二叉树的root。返回在不触动报警的情况下，小偷能够盗取的最该金额。

示例

image.png

输入：root = [3,2,3,null,3,null,1]
输出： 7
解释：小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

思路方法

利用动态规划和递归的结合算法。
根据规则我们可以发现，对于每一个节点，我们只关心它的孩子节点们的select与notSlect值。我们可以设计一个结构，表示某个节点的select与notSelect值，在每次递归返回的时候，都把这个点对应的select和notSelect返回给上一级调用，这样可以省去哈希表的空间。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int[] rootStatus = dfs(root);
        return Math.max(rootStatus[0],rootStatus[1]);
    }
    public int[] dfs(TreeNode root){
        if(root==null){
            return new int[]{0,0};
        }
        int[] l = dfs(root.left);
        int[] r = dfs(root.right);
        int select = root.val+l[1]+r[1];
        int notSelect = Math.max(l[0],l[1])+Math.max(r[0],r[1]);
        return new int[]{select,notSelect};
    }
}