python3 解法, 执行用时: 1504 ms, 内存消耗: 166.4 MB, 提交时间: 2023-10-25 07:49:54

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def getMaxLayerSum(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if node.left is None and node.right is None:
                return [node.val], [node.val], 0, True
            elif node.left is None or node.right is None:
                child = node.left or node.right
                nohit, hit, move_up_range, last_null = dfs(child)
                nohit.append(node.val)
                hit.append(node.val)
                for i in range(-1, -1 - move_up_range, -1):
                    hit[i] = max(hit[i], nohit[i - 1])
                if len(hit) - 1 - move_up_range > 0:
                    hit[len(hit) - 1 - move_up_range] = max(hit[len(hit) - 1 - move_up_range], nohit[len(hit) - 2 - move_up_range])
                #print("dfs1", node.val, nohit, hit)
                return nohit, hit, 0, True
            else:
                left_result = dfs(node.left)
                right_result = dfs(node.right)
                if len(left_result[0]) < len(right_result[0]):
                    left_result, right_result = right_result, left_result
                nohit_left, hit_left, move_up_range_left, last_null_left = left_result
                nohit_right, hit_right, _, last_null_right = right_result
                for i in range(len(hit_right)):
                    hr = hit_right[i]
                    if i == 0 and last_null_right:
                        hr = max(hr, 0)
                    j = len(hit_left) - len(hit_right) + i
                    hl = hit_left[j]
                    if j == 0 and last_null_left:
                        hl = max(hl, 0)
                    hit_left[j] = max(hl + nohit_right[i], nohit_left[j] + hr)
                for i in range(len(nohit_right)):
                    j = len(hit_left) - len(hit_right) + i
                    nohit_left[j] += nohit_right[i]
                last_null = (len(hit_left) > len(hit_right)) and last_null_left
                nohit_left.append(node.val)
                hit_left.append(node.val)
                move_up_range = max(move_up_range_left, len(nohit_right)) + 1
                #print("dfs2", node.val, nohit_left, hit_left, move_up_range, last_null)
                return nohit_left, hit_left, move_up_range, last_null

        _, hit, _, _ = dfs(root)
        return max(hit)

cpp 解法, 执行用时: 680 ms, 内存消耗: 433.3 MB, 提交时间: 2023-10-25 07:49:04

class Solution {
public:
    vector<vector<tuple<int, int, int, int>>> level_infs; /* 前缀和，占用，左下指针，右下指针 */
    vector<pair<int, int>> remove_list;
    int collect(int level, TreeNode* node) {
        if(!node) 
            return 0;

        while(level + 1 >= level_infs.size())
            level_infs.push_back({{0, -1, -1, -1}});

        level_infs[level].emplace_back(
            get<0>(level_infs[level].back()) + node->val, /* 前缀和 */
            -1, /* 被占用的情况 */
            level_infs[level+1].size(), /* 左侧向下指针 */
            -1 /* 右侧向下指针(需要等遍历完之后再补充) */
        );
        node->val = level_infs[level].size() - 1;

        if(collect(level + 1, node->left) + collect(level + 1, node->right) != 2) 
            remove_list.emplace_back((int)level_infs[level].size() - 1, level);
        
        get<3>(level_infs[level].back()) = (int)level_infs[level + 1].size() - 1;

        return 1;
    }
    int getMaxLayerSum(TreeNode* root) {
        collect(0, root);

        int height = (int)level_infs.size() - 1, res = INT_MIN;
        for(int level = 0; level < height; ++level)
            res = max(res, get<0>(level_infs[level].back()));

        for(int idx = 0; idx < remove_list.size(); ++idx) {
            auto [node, start] = remove_list[idx];
            int left = node, right = node;
            int lost = get<0>(level_infs[start][left]) - get<0>(level_infs[start][left-1]);
            for(int level = start; level < height; ++level) {
                if(left > right) 
                    break;

                /* 如果当前 "管辖区间" 为整层的节点，那么没有必要继续遍历下去，它相当于删除该层 */
                /* 另外，这个优化还能避坑 "如果最后一层全删掉，那么这个和为 0 是没有意义的" */
                if(right - left + 1 == level_infs[level].size() - 1)
                    break;

                auto& [lsum, luse, ne_left, _unused1] = level_infs[level][left];
                auto& [rsum, ruse, _unused2, ne_right] = level_infs[level][right];

                /* 剪枝：如果当前区间已经被使用过，则跳过后续部分 */
                if(luse != -1 && luse == ruse)
                    break;
                luse = ruse = idx;

                int add = 0;
                if(ne_left <= ne_right)
                    add = get<0>(level_infs[level+1][ne_right]) - get<0>(level_infs[level+1][ne_left - 1]);

                res = max(res, get<0>(level_infs[level].back()) - lost + add);

                left = ne_left, right = ne_right, lost = add;
            }
        }

        return res;
    }
};

cpp 解法, 执行用时: 1276 ms, 内存消耗: 749.8 MB, 提交时间: 2023-10-25 07:48:37

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

const int MAXD = 1e5;
int flag, used[MAXD + 10];

class Solution {
    typedef pair<long long, int> pli;
    vector<long long> sm;
    vector<int> sz;
    long long ans;

    // 先计算每个点的深度，以及统计每一层原有的和
    void dfs1(TreeNode *node, int d) {
        if (node == nullptr) return;
        if (sm.size() <= d) sm.push_back(0), sz.push_back(0);
        sm[d] += node->val;
        sz[d]++;
        dfs1(node->left, d + 1);
        dfs1(node->right, d + 1);
    }

    struct Result {
        // diff[i].first 表示深度 D - i 的变化值，diff[i].second 表示深度 D - i 的节点变化数量
        int D;
        vector<pli> diff;
        // 哪些深度的答案有待计入答案
        vector<int> pending;

        // 合并两个 Result
        void merge(Result &r) {
            // 这里能把 unordered_map 改成 vector，用到了一个特性：
            // 两个合并的 Result 里的最小深度是一样的
            assert(D - diff.size() == r.D - r.diff.size());
            if (diff.size() < r.diff.size()) swap(D, r.D), swap(diff, r.diff);
            for (int i = 1; i <= r.diff.size(); i++) {
                auto &p = diff[diff.size() - i];
                auto &q = r.diff[r.diff.size() - i];
                p.first += q.first;
                p.second += q.second;
                // 深度 D - diff.size() + i 的结果更新了，等待计入答案
                pending.push_back(D - diff.size() + i);
            }
            if (pending.size() < r.pending.size()) swap(pending, r.pending);
            for (int x : r.pending) pending.push_back(x);
        }
    };

    Result dfs2(TreeNode *node, int d) {
        if (node->left == nullptr && node->right == nullptr) {
            // 叶子节点
            Result ret;
            ret.D = d;
            if (sz[d] > 1) {
                // 删掉这个叶子节点不会掏空这一层，允许统计答案
                ans = max(ans, sm[d] - node->val);
                ret.diff.push_back(pli(-node->val, -1));
            } else {
                ret.diff.push_back(pli(0, 0));
            }
            return ret;
        } else if (node->left != nullptr && node->right != nullptr) {
            // 两个子节点
            Result a = dfs2(node->left, d + 1);
            Result b = dfs2(node->right, d + 1);
            a.merge(b);

            // 自己这层的变化量也要算
            a.diff.push_back(pli(node->left->val + node->right->val - node->val, 1));
            // 不能马上计算答案（因为这个点有两个子节点，不能删掉），先记下来
            a.pending.push_back(d);
            return a;
        } else {
            // 只有一个子节点
            TreeNode *ch = node->left == nullptr ? node->right : node->left;
            Result ret = dfs2(ch, d + 1);
            // 删掉这个子节点，开始统计所有受影响的层的答案
            flag++;
            for (int x : ret.pending) if (used[x] != flag) {
                used[x] = flag;
                pli p = ret.diff[ret.D - x];
                // 深度 x 的变化不能导致深度 x 整层被掏空
                if (sz[x] + p.second > 0) ans = max(ans, sm[x] + p.first);
            }
            ret.pending.clear();

            // 自己这层的变化量也要算
            long long delta = ch->val - node->val;
            ans = max(ans, sm[d] + delta);
            ret.diff.push_back(pli(delta, 0));
            return ret;
        }
    }

public:
    int getMaxLayerSum(TreeNode* root) {
        dfs1(root, 0);
        ans = sm[0];
        for (long long x : sm) ans = max(ans, x);
        dfs2(root, 0);
        return ans;
    }
};