text: # Time:  O(n)
  # Space: O(h)
  
  # 337
  # The thief has found himself a new place for his thievery again.
  # There is only one entrance to this area, called the "root."
  # Besides the root, each house has one and only one parent house.
  # After a tour, the smart thief realized that "all houses in this
  # place forms a binary tree". It will automatically contact the
  # police if two directly-linked houses were broken into on the
  # same night.
  #
  # Determine the maximum amount of money the thief can rob tonight
  # without alerting the police.
  #
  # Example 1:
  #      3
  #     / \
  #   2   3
  #     \   \
  #      3   1
  # Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
  # Example 2:
  #      3
  #     / \
  #   4   5
  #   / \   \
  #  1   3   1
  # Maximum amount of money the thief can rob = 4 + 5 = 9.
  #
  # Definition for a binary tree node.
  # class TreeNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution(object):
      def rob(self, root):
          """
          :type root: TreeNode
          :rtype: int
          """
          def robHelper(root):
              if not root:
                  return (0, 0)
              lTake, lSkip = robHelper(root.left)
              rTake, rSkip = robHelper(root.right)
              return root.val + lSkip + rSkip, max(lTake, lSkip) + max(rTake, rSkip)
  
          return max(robHelper(root))
  