[Python] very short dfs, explained
If you already solved House Robber I or II, you probably aware, that this problem is about dp. However, let us look at it from a bit different point of view, it
If you already solved House Robber I or II, you probably aware, that this problem is about dp. However, let us look at it from a bit different point of view, it will be much easier to digest: let us use dfs and for each node we will keep two values:\n1. Maximum gain we can get if we already visited all subtree given node, if we rob given node.\n2. Maximum gain, we can get if we already visited all subtree given node, if we do not rob given node.\n\nHow we can find it, using recursion now?\nImagine, that we have `node` and `L` and `R` are left and right children. Then:\n1. If we rob given node, than we can not rob children, so answer will be `node.val + L[1] + R[1]`\n2. If we do not rob house, we have two options for `L` and two options for `R`, and we choose the best ones, so we have `max(L) + max(R)`.\n\n**Complexity**: time complexity is `O(n)`, because we visit all our tree. Space complexity is `O(h)`, because we use recursion.\n\n```\nclass Solution:\n    def rob(self, root):\n        def dfs(node):\n            if not node: return [0, 0]\n            L = dfs(node.left)\n            R = dfs(node.right)\n            return [node.val + L[1] + R[1], max(L) + max(R)]\n        \n        return max(dfs(root))\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Depth-First Search']