打家劫舍系列 1，2，3

打家劫舍3
https://leetcode-cn.com/problems/house-robber-iii/submissions/
这里加了二叉树的限制
对于二叉树，我们用dfs深度优先遍历去做。
这里很重要的一个技巧是用了2个数组存储当前节点选择，或者不选的最大收益。
对于递归，关注的要点是：

1. 返回值：
   1）如果root为空的，那么只能返回[0,0]，其中第一个0表示不选的最大收益，第二个0表示选择的最大收益。
   2） 如果不为空，那么对于当前root节点来说，不选择他，有2种情况可以考虑----下一层选择，或者不选择，对于这两种情况求个最大值，作为不选择当前root节点的值。如果选择了当前root节点，下一层只能不做选择了，并且加上当前自己的值。
2. 注意递归的时机和选择。
   代码如下：

class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        result = self.dns(root)
        return max(result[0],result[1])
    
        
    def dns(self,root):
        if not root:
            return [0,0]
        left = self.dns(root.left)
        right = self.dns(root.right)
        result = [0,0]
        result[0] = max(left[0],left[1]) + max(right[0],right[1]) # 不选当前层的话，下一层有选或者不选两种选择，取其最大值
        result[1] = root.val + left[0] + right[0] # 选了当前层，那么下一层只能放弃了
        return result