How to solve House Robber III -Leetcode -337

In this Leetcode Problem, we have to determine the maximum amount of money a thief can rob without alerting the police.

So we see that the thief can only rob the houses which are not linked with a direct parent.

Therefore the approach to the problem should be :

1. Start with the root, and traverse through the nodes.
2. While considering each level of tree, both the left and right nodes are added to the result.
3. If the root node is considered then consider the grandchild nodes and leave out the child nodes.
4. If the 2nd level node(i.e. the child nodes) are considered, then leave its immediate child nodes and consider its grand child nodes.
5. Traverse through the binary tree in a recursive way.
6. Produce the result as either of the Maximum of root level or its immediate child level summation.

Here is the entire code :

class Solution {
 public int rob(TreeNode root) {
 if(root == null)
 return 0;
 
 int[] result = helper(root);
 return Math.max(result[0], result[1]);
}
 
public int[] helper(TreeNode root){
 if(root == null){
 int[] result = {0, 0};
 return result;
 }
 
 int[] result = new int[2];
 int[] left = helper(root.left);
 int[] right = helper (root.right);
 
 // result[0] is when root is selected, result[1] is when not. 
 result[0] = root.val + left[1] + right[1];
 result[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
 
 return result;
 }
}

Time complexity is O(n).

Happy Coding :)