337: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nThe problem can be solved using a recursive approach. We can traverse the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThe problem can be solved using a recursive approach. We can traverse the binary tree in a post-order traversal. At each node, we need to decide whether to rob the node or not.\n\nLet\'s define a helper function dfs which returns two values - robThis and notRobThis. robThis represents the maximum amount that can be robbed if we choose to rob the current node, and notRobThis represents the maximum amount that can be robbed if we choose not to rob the current node.\n\nTo calculate robThis, we need to add the value of the current node and the value of the grandchildren nodes (the nodes which are two levels below the current node) to notRobGrandChildren. To calculate notRobThis, we need to add the maximum of robGrandChildren and notRobGrandChildren.\n\nThe base case for the recursion is when the node is None, in which case we return (0, 0).\n\nAt the root node, we need to return the maximum of robThis and notRobThis.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def rob(self, root: Optional[TreeNode]) -> int:\n        # Define the helper function\n        def dfs(node):\n            # Base case: if the node is None, return (0, 0)\n            if not node:\n                return (0, 0)\n            \n            # Recursive case: calculate the values for the left and right subtrees\n            left_rob, left_not_rob = dfs(node.left)\n            right_rob, right_not_rob = dfs(node.right)\n            \n            # Calculate the values for the current node\n            rob_this = node.val + left_not_rob + right_not_rob\n            not_rob_this = max(left_rob, left_not_rob) + max(right_rob, right_not_rob)\n            \n            # Return the values for the current node\n            return (rob_this, not_rob_this)\n        \n        # Call the helper function on the root node and return the maximum value\n        return max(dfs(root))\n\n```
['Dynamic Programming', 'Tree', 'Depth-First Search', 'Python', 'Python3']