337.House RobberIII

发表于 | 分类于

题目详见：https://leetcode.com/problems/house-robber-iii/

思路：深度搜索。两种情况：根节点rob，下一层的子节点必定不会rob；根节点不rob，下一层的左右子节点可rob也可不rob，取max(robLeft,notRobLeft)+max(robRight,notRobRight)作为根节点不rob所得的最大money。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int rob(TreeNode* root) {
        if(!root) return 0;
        int rob,notRob;
        dfs(root,rob,notRob);
        return max(rob,notRob);
    }
private:
    void dfs(TreeNode* root,int& rob,int& notRob){
        if(!root){
            rob=0;
            notRob=0;
            return;
        }
        dfs(root->left,rob,notRob);
        int x,y;
        dfs(root->right,x,y);
        int tmp=rob;
        rob=root->val+notRob+y;
        notRob=max(tmp,notRob)+max(x,y);
    }
    
};