337. House Robber III 发表于 2022-10-06 DFS + Cache1234567891011121314151617181920212223242526272829303132333435363738394041424344class Solution { public int rob(TreeNode root) { Map<TreeNode, Integer> notRobMoneyCache = new IdentityHashMap<>(); Map<TreeNode, Integer> robMoneyCache = new IdentityHashMap<>(); return rob(root, false, notRobMoneyCache, robMoneyCache); } private int rob(TreeNode node, boolean parentRobbed, Map<TreeNode, Integer> notRobMoneyCache, Map<TreeNode, Integer> robMoneyCache) { if (node == null) { return 0; } // not rob node Integer cachedNotRobMoney = notRobMoneyCache.get(node); int notRobMoney; if (cachedNotRobMoney != null) { notRobMoney = cachedNotRobMoney; } else { notRobMoney = rob(node.left, false, notRobMoneyCache, robMoneyCache) + rob(node.right, false, notRobMoneyCache, robMoneyCache); notRobMoneyCache.put(node, notRobMoney); } // rob node int robMoney = 0; if (!parentRobbed) { Integer cachedRobMoney = robMoneyCache.get(node); if (cachedRobMoney != null) { robMoney = cachedRobMoney; } else { robMoney += node.val; if (node.left != null) { robMoney += rob(node.left, true, notRobMoneyCache, robMoneyCache); } if (node.right != null) { robMoney += rob(node.right, true, notRobMoneyCache, robMoneyCache); } robMoneyCache.put(node, robMoney); } } return Math.max(notRobMoney, robMoney); }} DFS1234567891011121314151617181920212223class Solution { public int rob(TreeNode root) { int[] res = dfs(root); return Math.max(res[0], res[1]); } private int[] dfs(TreeNode root) { if (root == null) { return new int[2]; } int[] left = dfs(root.left); int[] right = dfs(root.right); // 注意此处,不偷窃当前节点时,子节点可以被偷窃,也可以不被偷窃,也可以其中一个子节点被偷窃,另一个不被偷窃 int notRob = left[1] + right[1]; notRob = Math.max(notRob, left[0] + right[0]); notRob = Math.max(notRob, left[0] + right[1]); notRob = Math.max(notRob, left[1] + right[0]); int rob = root.val + left[0] + right[0]; return new int[]{notRob, rob}; }} DFS1234567891011121314151617181920class Solution { public int rob(TreeNode root) { int[] res = dfs(root); return Math.max(res[0], res[1]); } private int[] dfs(TreeNode root) { if (root == null) { return new int[2]; } int[] left = dfs(root.left); int[] right = dfs(root.right); // 注意此处,不偷窃当前节点时,此树能偷窃到的最大金额等于左子树能够偷窃到的最大金额加上右子树能偷窃到的最大金额 int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); int rob = root.val + left[0] + right[0]; return new int[]{notRob, rob}; }} Reference337. House Robber III