Untitled
// pick not pick pattern // include exclude pattern // take not take pattern public class HouseRobberIII { public int rob(TreeNode root) { int[] result = dfs(root); return Math.max(result[0], result[1]); } // Returns an array where: // result[0] = max amount when robbing the current node // result[1] = max amount when not robbing the current node private int[] dfs(TreeNode node) { if (node == null) { return new int[]{0, 0}; } // Post-order traversal: process left and right children first int[] left = dfs(node.left); int[] right = dfs(node.right); // If we rob the current node, we cannot rob its children int robCurrent = node.val + left[1] + right[1]; // If we do not rob the current node, we take the max from children int notRobCurrent = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); return new int[]{robCurrent, notRobCurrent}; }
Leave a Comment