树形DP

树形DP一般都是在树上做DP

$ 时间复杂度O(N) $

参考文献

lc究极班

AC代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> dfs(TreeNode* u){
        //空
        if (!u) return {0, 0};
        vector<int> f(2, 0);
        auto l = dfs(u->left), r = dfs(u->right);
        //不选
        f[0] = max(l[0], l[1]) + max(r[0], r[1]);
        //选
        f[1] = l[0] + r[0] + u->val;
        return f;
    }

    int rob(TreeNode* root) {
        auto f = dfs(root);
        return max(f[0], f[1]);
    }
};