설명

예시 1

입력

root = [1, [4, [3, null, null], [2, null, null]], [5, null, null]]

산출

10

설명

We can pick 3, 2 and 5. Note if we picked 4, we wouldn't be able to pick 3 and 2 since they are adjacent.

직관

구현

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */

pair<int, int> dfs(Tree* node) {
    if (!node) return make_pair(0, 0);
    auto [leftWith, leftWithout] = dfs(node->left);
    auto [rightWith, rightWithout] = dfs(node->right);

    int withRoot = leftWithout + rightWithout + node->val;
    int withoutRoot = max(leftWith, leftWithout) + max(rightWith, rightWithout);

    return make_pair(withRoot, withoutRoot);
}
int solve(Tree* root) {
    auto [with, without] = dfs(root);
    return max(with, without);
}

시간 복잡도