[Python3] Easy to understand | Recursive Post-order | Linear time & space
Intuition\nAt each node, we either need to consider the node iteslf or its children.\n\n# Approach\nFrom each node, return the max we can get by including the n
# Intuition\nAt each node, we either need to consider the node iteslf or its children.\n\n# Approach\nFrom each node, return the max we can get by including the node and also max without the node.\n\n1. For base cases (Leaf node\'s Null children), return `[0, 0]`\n2. With postorder traversal, at each node up in recusrsion calculate the following and return:\n\n```\nwithCurrentNode = node.val + leftSubtreeMaxWithoutRoot + rightSubtreeMaxWithoutRoot\n\nwithoutCurrentNode = max(leftSubtreeMaxWithRoot, leftSubtreeMaxWithoutRoot) + max(rightSubtreeMaxWithRoot, rightSubtreeMaxWithoutRoot)\n```\n\n# Complexity\n- Time complexity:\nO(N) - We need to look at all the nodes once\n- Space complexity:\nO(H) Space - H being the height of the tree. For an unbalanced tree, this will be O(N) Space. The space is for maintaining the call stack\n\n# Code\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def rob(self, root: Optional[TreeNode]) -> int:\n\n        def postorder(root):\n            if not root:\n                return [0, 0]   # [ withRoot, withoutRoot ]\n            \n            left = postorder(root.left)\n            right = postorder(root.right)\n\n            withRoot = root.val + left [1] + right[1]\n            withoutRoot = max(left) + max(right)\n            return [withRoot, withoutRoot]\n        \n        return max(postorder(root))\n```
['Python3']