原文标题写着”逆中序遍历”，对应的题目其实是「所有大于等于节点的值之和」。这里把题意和反向中序遍历的思想补一下，代码保留原样。

题目背景

剑指 Offer II 054 / LeetCode 538「把二叉搜索树转换为累加树」。给一棵 BST，把每个节点的值替换为”原 BST 中所有大于等于该节点值的节点之和”。

概念解释

BST 性质：左子树所有值 < 根 < 右子树所有值。
正向中序：左 → 根 → 右，遍历结果是升序。
反向中序（逆中序）：右 → 根 → 左，遍历结果是降序。这个序列正好是”按 ≥ 当前节点的顺序”逐个访问，非常适合做累加。

实现原理

只要按”右、根、左”的顺序遍历，每遍历到一个节点时，把当前的累加和 sum 加上它自己的值，再把 sum 写回给该节点，就完成了”把当前节点替换为所有 ≥ 它的值之和”。

inverse_inorder(right);
sum += root->val;
root->val = sum;
inverse_inorder(left);

由于反向中序保证了”所有大于当前节点的节点都已经先被加进 sum“，所以累加结果天然正确。

时间复杂度 O(n)，每个节点只被访问一次；空间复杂度 O(h) 为递归栈深度。

参考实现

剑指 Offer II 054. 所有大于等于节点的值之和

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    void inverse_inorder(TreeNode* root, int& sum)
    {
        if(root == nullptr)
        {
            return;
        }

        inverse_inorder(root->right, sum);
        sum += root->val;
        root->val = sum;
        inverse_inorder(root->left, sum);
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        inverse_inorder(root, sum);
        return root;
    }
};

FEATURED TAGS

Git Cheat Sheet Markdown Tools C++ Linker Thread Linux TCP Network GDB Debug leetcode 链表 WSL Ubuntu Windows Linux Kernel GCC Android adb Troubleshooting Profiling Sanitizer glibc MySQL Database Python curl Build ELF clang-format CMake Graphviz Performance vcpkg Protobuf 排查速查内存 STL 调试性能分析性能读书笔记方法论架构网络 Timer mbedTLS TLS 安全负载均衡脚本工具 LRU 二叉树 BST 中序遍历回溯二分查找优先队列排序旋转数组 jenkins 部署

把二叉搜索树转换为累加树（反向中序）

剑指 Offer II 054 / LeetCode 538 题解笔记

CATALOG