README.md

recursion

We can use recursion to solve the problem.
input: subtree root
return: both rob this root max value and unrob this root max value
induction rule:

1. rob = left.unrob + right.unrob + root.val
2. unrob = Math.max(left.rob, left.unrob) + Maht.max(right.rob, right.unrob)

time: O(n)
space: O(height)

backtrakcing + memoization

return: max money of the substree of that root induction rule:
rob = root.val
if left != null: rob += rob(root.left.left) + rob(root.left.right)
if right != null: rob += rob(root.right.left) + rob(root.right.right)
notRob = rob(root.left) + rob(root.right)
return max(rob, notRob)

time: O(n)
space: O(n)