class Solution:
    def rob(self, root: TreeNode) -> int:
        def _rob(root):
            if not root: return 0, 0  # 偷，不偷
            left = _rob(root.left)
            right = _rob(root.right)
            # 偷当前节点, 则左右子树都不能偷
            v1 = root.val + left[1] + right[1]
            # 不偷当前节点, 则取左右子树中最大的值
            v2 = max(left) + max(right)
            return v1, v2
        return max(_rob(root))

树，动态规划，中等

https://leetcode-cn.com/problems/house-robber-iii/

做这题的心路历程：

👉好像就是一层一层选

👉那我先层序遍历算出每层的值，再隔一行选，看是奇数行还是偶数行大

👉 诶怎么会有4->1->2->3这样神奇的排列

👉 那按照动态规划求解

👉 怎么又有 [2,1,3,null,4] 这样的树。。。

👉 看答案。。。噢！