题解 | #打家劫舍(三)#

针对每个节点，有两种情况，选，或者不选，而该点的最大值为可以分为两种情况，选择该点时和不选择该点时，如果不选择该点，只需要获得左右子节点的最大值并相加，如果需要选择点，则需要获左右子节点都不直接选择的最大值（所以每次递归需要把子节点不选择时的最大值也返回上来）。最后比较两种情况的大小返回真正的最大值即可

int rob(TreeNode* root) {
    int allMax = 0;
    int noSelect = 0;
    check(root, allMax, noSelect);
    return allMax;
}

// 每次返回不选择改节点能取到的最大值，以及不管选不选的实际最大值
void check(TreeNode* node, int& allMax, int& noSelect) {
    if (node == nullptr) {
        return;
    }
    int leftMax = 0;
    int leftNoSelect = 0;
    int rightMax = 0;
    int rightNoSelect = 0;
    check(node->left, leftMax, leftNoSelect);
    check(node->right, rightMax, rightNoSelect);
    
    // 不选该点的最大值为：左儿子的最大值 + 右儿子的最大值
    noSelect = leftMax + rightMax;
    // 该点的实际最大值为max(不选择该点的最大值, 左儿子不被选择时的最大值 + 右儿子不被选择的最大值 + 该点的最大值）
    allMax = max(noSelect, node->val + leftNoSelect + rightNoSelect);
}