算法

(树上DP) $O(n)$

这题可以用树上的动态规划求解，对于每个节点，如果我们知道子节点中抢或不抢的子树中的最大值，就可以计算出当前节点抢或不抢的最大值。且一个父节点的决策对于子节点抢或不抢的决策的最大值没有影响，这满足了动态规划的无后效性和最优子结构，所以可以用动态规划求解。

C++ 代码

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> dp = dfs(root);
        return max(dp[0], dp[1]);
    }

    // 得到的dp数组，dp[0]代表不抢的最大值，dp[1]代表抢的最大值
    vector<int> dfs(TreeNode * root) {
        vector<int> dp(2, 0);
        if (root == nullptr) {
            return dp;
        }

        // 分别获得左右子树的信息值
        vector<int> leftDp = dfs(root -> left);
        vector<int> rightDp = dfs(root -> right);

        // 根据左右子树的信息值，计算当前节点抢或不抢的最大值
        dp[0] = max(leftDp[0], leftDp[1]) + max(rightDp[0], rightDp[1]);
        dp[1] = (root -> val) + leftDp[0] + rightDp[0];

        return dp;
    }
};