- 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为 root 。
- 除了 root 之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警。
- 给定二叉树的 root 。返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 。
链接:https://leetcode-cn.com/problems/house-robber-iii
分析:该题通过考虑偷不偷根节点来考虑
/** * 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 { class ReturnType{ int stealMax; int notStealMax; public ReturnType() { } public ReturnType(int stealMax, int notStealMax) { this.stealMax = stealMax; this.notStealMax = notStealMax; } } public int rob(TreeNode root) { if (root == null) { return 0; } // 只有一个节点时只能偷了 if (root.left == null && root.right == null) { return root.val; } ReturnType result = process(root); return Math.max(result.notStealMax, result.stealMax); } private ReturnType process(TreeNode root) { if (root == null) { return new ReturnType(0,0); } ReturnType leftReturn = process(root.left); ReturnType rightReturn = process(root.right); // 偷root int stealRoot = root.val + leftReturn.notStealMax + rightReturn.notStealMax; // 不偷root int notStealRoot = Math.max(leftReturn.notStealMax, leftReturn.stealMax) + Math.max(rightReturn.notStealMax, rightReturn.stealMax); return new ReturnType(stealRoot,notStealRoot); } }