[Python3] Dynamic Programming + Depth First Search
we construct a dp tree, each node in dp tree represents [rob the current node how much you gain, skip the current node how much you gain]\n dp_node[0] =[rob the
* we construct a dp tree, each node in dp tree represents [rob the current node how much you gain, skip the current node how much you gain]\n dp_node[0] =[rob the current node how much you gain]\n dp_node[1] =[skip the current node how much you gain]\n* we start the stolen from the leaf: Depth First Search\n* for each node you have 2 opitions:\n\toption 1: rob the node, then you can\'t rob the child of the node.\n\t\t\t\t\tdp_node[0] = node.val + dp_node.left[1] +dp_node.right[1]\n\toption 2: skip the node, then you can rob or skip the child of the node. \n\t\t\t\t\tdp_node[1] = dp_node.left[0] + dp_node.right[0]\n* \tthe maximum of gain of the node depents on max(dp_node[0],dp_node[1])\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, x):\n#         self.val = x\n#         self.left = None\n#         self.right = None\n\nclass Solution:\n    """\n    Input: [3,4,5,1,3,null,1]\n input tree            dp tree:\n     3                  [3+3+1,4+5]\n    / \\                /        \\\n   4   5            [4,3]      [5,1]\n  / \\   \\          /     \\          \\\n 1   2   1      [1,0]    [2,0]     [1,0]\n                / \\       /  \\        /  \\\n           [0,0] [0,0] [0,0] [0,0]  [0,0] [0,0]\n    \n    """\n    def rob(self, root: TreeNode) -> int:\n        return max(self.dfs(root))\n    \n    def dfs(self, root: TreeNode):\n        if not root:\n            return (0, 0)\n        left = self.dfs(root.left)\n        right = self.dfs(root.right)\n        return (root.val + left[1] + right[1], max(left[0], left[1]) + max(right[0], right[1]))\n```
['Dynamic Programming', 'Depth-First Search', 'Python', 'Python3']