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);
}