337. 打家劫舍 III(leetcode)

LXL's Blog / 2024-09-05 / 原文

https://leetcode.cn/problems/house-robber-iii/description/
基础树形dp,要点是f的定义
灵神讲的很好:https://www.bilibili.com/video/BV1vu4y1f7dn/?vd_source=1bb76d0400eba0d49ad4c1dd07bc4249

/**
 * 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) {
        // 树形dp
        // 根据每一个节点都有选与不选两种状态,以此来作为f定义,划分子集
        // 以是否选择当前节点来划分子集
        // dfs(i)表示以i为根节点获取的最大金额
        // dfs(i)=
        // 1.选i这个节点,则为 left[1]+right[1]+node.val; //1表示不偷当前节点获得的最大金额,0表示偷
        // 2.不选,则为 max(left[0],left[1]) + max(right[0],right[1]);
        int[] res=dfs(root);
        return Math.max(res[0],res[1]);
    }

    // 后序遍历,从下到上依次计算递推,返回值是两个子集,需要求max
    int[] dfs(TreeNode root)
    {
        if(root == null)return new int[]{0,0};// 没有节点,则最大金额为0
        int[] left=dfs(root.left);
        int[] right=dfs(root.right);
        int v1=left[1] + right[1] + root.val; // 选当前节点
        int v2=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        return new int[]{v1,v2}; // 第一位是选当前节点,第二位是不选
    }
}