题意理解

相比于前面两题，这里把房子的布局设置为二叉树的形式。现在要求选择数字的时候，父结点和孩子结点不能同时选。

方法一

深度优先搜索
对于某个结点，可以选择或者不选，我们通过深度优先搜索遍历出每种可能的情况，并计算出对应结点数字的总和。如果选择当前结点，那么以它为根结点的数字总和为它本身加上以其左右孩子为根（且不选择其左右孩子）的数字总和；如果不选择当前结点，那么以它为根结点（不选择）的数字总和为以其左右孩子为根的数字总和。这样就形成了一个递归过程。

我们使用map类型num来表示每个结点在选或者不选的时候，对应的数字总和的最大值；其中索引为由结点和布尔型构成的$pairpair$。

但是，当不选择父结点时，孩子结点是可选的而不是必选的。我们可能多次计算孩子结点不选的情况，重复了。所以要加一个判断，如果已经计算过的num就直接返回值。

以{2,1,2,#,2,#,1}为例，通过计算得到的num如下：

具体代码如下：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    map<pair<TreeNode* , bool>, int> num;
    int search(TreeNode* p, bool select)
    {
        if (p == NULL) return 0;
        if (num.count({p,select})) return num[{p,select}];
        //不偷当前这家
        num[{p,false}] = search(p->left,true) + search(p->right,true);
        //偷当前这家
        if (select)
        { 
            num[{p,true}] = p->val + search(p->left, false) + search(p->right, false);
            return max(num[{p,true}], num[{p,false}]);
        }
        return num[{p,false}];
    }
    
    int rob(TreeNode* root) {
        // write code here
        return search(root, true);
    }
};

时间复杂度： $O(N)O(N)$。因为判断了当前num是否出现过，避免了一些不必要的重复计算，每个num[{指针,true/false}]计算一次，一共计算了2N次。
空间复杂度： $O(N)O(N)$。开辟了新的map类型的num，其长度为N。

方法二

如果不想判断某个num是否已经计算过了，可以调整一下递归的顺序，先递归到叶子结点（不计算），再从下往上（从叶子结点相根结点）进行计算。这样可以保证不重复计算。

具体代码如下：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    map<pair<TreeNode* , bool>, int> num;
    void search(TreeNode* p)
    {
        if (p == NULL) return;
        //先遍历到叶子结点
        search(p->left);
        search(p->right);
        //再分别计算是否选取当前结点的数字对应的num
        num[{p,true}] = p->val + num[{p->left,false}] + num[{p->right,false}];
        int l = max(num[{p->left,true}], num[{p->left,false}]);
        int r = max(num[{p->right,true}], num[{p->right,false}]);
        num[{p,false}] = l + r;
    }
    
    int rob(TreeNode* root) {
        // write code here
        search(root);
        return max(num[{root,true}], num[{root,false}]);
    }
};

时间复杂度： $O(N)O(N)$。由下往上对每个结点计算两次，一共也是2N次。
空间复杂度： $O(N)O(N)$。开辟了新的map类型的num，其长度为N。