当前位置：首页 > article >正文

Leetcode 337 打家劫舍 III

article 2024/11/14 20:47:25

题意理解：

        小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

        给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额。



这里的打家劫舍不同之处在于：状态转移是在一颗树上

限制要求是：相邻不能偷

所以：

偷了根节点，左右孩子节点不能偷

偷了左右孩子，根节点不能偷

解题思路：

这里使用回溯法来遍历每个节点

每个节点都有两种状态：偷当前节点，和不偷当前节点

所以我们在每层设置一个dp数组： dp[0]表示不偷所能获得的最大金额， dp[1]表示偷所能获得的最大金额。

所以每层返回一个dp数组。

dp[0]=max(偷左，不偷左）+ max(偷右，不偷右)

dp[1]=不偷左+不偷右+根

最后的结果是：

max(dp[0],dp[1])

1.解题

    public int rob(TreeNode root) {
        int[] dp=new int[2];
        dp=travel(root);
        return Math.max(dp[0],dp[1]);
    }

    public int[] travel(TreeNode root){
        int[] dp=new int[2];
        if(root==null) return dp;
        int[] left_dp=travel(root.left);
        int[] right_dp=travel(root.right);
        dp[0]=Math.max(left_dp[0],left_dp[1])+Math.max(right_dp[0],right_dp[1]);
        dp[1]=left_dp[0]+right_dp[0]+root.val;
        return dp;
    }