↓Skip to main content

【LeetCode 337】打家劫舍III

·213 words·1 min
WFUing
Author
WFUing
A graduate who loves coding.
Table of Contents

  • 链接：https://leetcode.cn/problems/house-robber-iii/description/

难点
#

很自然地想到是树状dp，分成两种情况，一种包含当前节点，另一种不包含。难点在于不包含的情况，不仅仅有左右孩子包含的情况，还有不包含的情况。

解析
#

代码
# 

/**
 * 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 {
    Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();

    public int rob(TreeNode root) {
        // 递归，传递状态而不是记录
        int[] res = robTree(root);
        return Math.max(res[0], res[1]);


        // 递归，记录状态
        // if(root == null) return 0;
        // if(root.left == null && root.right == null) return root.val;
        // if(map.containsKey(root)) return map.get(root);

        // // rob root
        // int val1 = root.val;
        // if(root.left != null) val1 += (rob(root.left.left) + rob(root.left.right));
        // if(root.right != null) val1 += (rob(root.right.left) + rob(root.right.right));

        // // not rob root
        // int val2 = 0;
        // val2 += (rob(root.left) + rob(root.right));

        // map.put(root, Math.max(val1, val2));
        // return Math.max(val1, val2);
    }

    public int[] robTree(TreeNode node) {
        int[] vals = new int[2];
        if(node == null) return vals;

        int[] l = robTree(node.left);
        int[] r = robTree(node.right);

        // 0 表示不偷 node
        vals[0] = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);

        // 1 表示偷 node
        vals[1] = node.val + l[0] + r[0];
        return vals;
    }
}