337. 打家劫舍 III

337. 打家劫舍 III

---

C代码：二叉树 + 动态规划

typedef struct  {  // 每个节点都有两个状态：选中、不选中
    int selected;
    int notSelected;
} SubtreeStatus;

SubtreeStatus dfs(struct TreeNode *node) {
    if (!node) {
        return (SubtreeStatus){0, 0};
    }
    SubtreeStatus l = dfs(node->left);
    SubtreeStatus r = dfs(node->right);
    int selected = node->val + l.notSelected + r.notSelected;  // 后序遍历，如果选中父节点，则子节点没有选中
                                                               // 父节点没有选中，则子节点可选中、可不选中；往上迭代！
    int notSelected = fmax(l.selected, l.notSelected) + fmax(r.selected, r.notSelected);

    return (SubtreeStatus){selected, notSelected};
}

int rob(struct TreeNode *root) {
    SubtreeStatus rootStatus = dfs(root);
    return fmax(rootStatus.selected, rootStatus.notSelected);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23