Sponsored
Sponsored
This approach uses recursion along with memoization to store the maximum robbery amount for each node of the tree. The idea is to leverage a helper function that returns two values for each node: maximum money if the current node is included and maximum money if the current node is not included. At each node, we have two choices: either rob this node or not rob it, and for each choice, there are further choices for child nodes and so on.
Time Complexity: O(N), where N is the number of nodes in the tree, as each node is visited only once. Space Complexity: O(N) due to the recursion stack space in the worst case of a skewed tree.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public int Rob(TreeNode root) {
10 var res = RobSub(root);
11 return Math.Max(res[0], res[1]);
12 }
13
14 private int[] RobSub(TreeNode node) {
15 if (node == null) return new int[2];
16
17 int[] left = RobSub(node.left);
18 int[] right = RobSub(node.right);
19
20 int rob = node.val + left[0] + right[0];
21 int notRob = Math.Max(left[0], left[1]) + Math.Max(right[0], right[1]);
22
23 return new int[] { notRob, rob };
24 }
25}In C#, recursion with an array storing two entry results for max robbery value by including or excluding the node. The RobSub method returns this max values from both the children nodes up till the parent nodes.