题目描述给定一棵二叉搜索树BST的根节点root树中节点值各不相同。要求将其转换为累加树Greater Sum Tree规则如下每个节点的新值 原节点值 所有比它大的节点值的总和二叉搜索树的性质左子树所有节点值 根节点值右子树所有节点值 根节点值中序遍历结果为升序序列核心思路逆中序遍历 累加要实现累加树关键是从大到小遍历所有节点边遍历边累加再更新当前节点的值。核心逻辑二叉搜索树的 ** 中序遍历左 - 根 - 右是升序那么逆中序遍历右 - 根 - 左** 就是降序。我们按降序遍历所有节点用一个变量sum记录遍历过的节点值总和每次访问一个节点时先更新sum加上当前节点值再把sum赋值给当前节点这样就能保证每个节点的值 原节点值 所有比它大的节点值的和完整代码实现Ccpp/** * 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 { public: // 全局变量记录遍历过程中的累加和 int sum 0; TreeNode* convertBST(TreeNode* root) { // 逆中序遍历右 - 根 - 左 if (root ! nullptr) { // 1. 先遍历右子树所有比当前节点大的节点 convertBST(root-right); // 2. 处理当前节点更新累加和并修改节点值 sum root-val; root-val sum; // 3. 再遍历左子树所有比当前节点小的节点 convertBST(root-left); } return root; } };详细执行流程解析我们以示例root [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]为例模拟逆中序遍历过程初始状态sum 0节点值升序0, 1, 2, 3, 4, 5, 6, 7, 8逆序遍历顺序8 → 7 → 6 → 5 → 4 → 3 → 2 → 1 → 0遍历过程访问节点8sum 8→sum 8root-val 8节点值更新为 8访问节点7sum 7→sum 15root-val 15节点值更新为 15访问节点6sum 6→sum 21root-val 21节点值更新为 21访问节点5sum 5→sum 26root-val 26节点值更新为 26访问节点4sum 4→sum 30root-val 30节点值更新为 30访问节点3sum 3→sum 33root-val 33节点值更新为 33访问节点2sum 2→sum 35root-val 35节点值更新为 35访问节点1sum 1→sum 36root-val 36节点值更新为 36访问节点0sum 0→sum 36root-val 36节点值更新为 36最终结果所有节点值更新为[30, 36, 21, 36, 35, 26, 15, null, null, null, 33, null, null, null, 8]和示例输出完全一致。关键细节与易错点逆中序遍历的顺序必须严格按照右子树 → 根节点 → 左子树的顺序遍历这样才能保证先访问所有比当前节点大的节点再更新当前节点的值。累加和变量sum的作用sum是一个全局变量或通过引用传递的变量记录所有已经访问过的节点值的总和每次更新节点值时直接赋值sum即可无需重复计算。空节点的处理当root nullptr时直接返回不做任何操作这是递归的终止条件。节点值的修改顺序必须先更新sum再修改root-val否则会导致节点值更新错误。复杂度分析时间复杂度\(O(n)\)其中 n 为树的节点数。每个节点只会被访问一次。空间复杂度\(O(h)\)其中 h 为树的高度。递归调用栈的深度等于树的高度最坏情况下树退化为链表为 \(O(n)\)。拓展迭代版实现可选如果不想使用递归可以用栈模拟逆中序遍历cppclass Solution { public: TreeNode* convertBST(TreeNode* root) { int sum 0; stackTreeNode* stk; TreeNode* cur root; // 逆中序遍历右-根-左 while (cur ! nullptr || !stk.empty()) { // 1. 一直向右走把所有右子树节点压入栈 while (cur ! nullptr) { stk.push(cur); cur cur-right; } // 2. 弹出栈顶节点当前访问的节点 cur stk.top(); stk.pop(); // 3. 更新累加和并修改节点值 sum cur-val; cur-val sum; // 4. 处理左子树 cur cur-left; } return root; } };总结将二叉搜索树转换为累加树的核心就是利用逆中序遍历的降序特性边遍历边累加更新节点值。这种方法无需额外空间仅通过一次遍历就能完成转换时间复杂度为线性是最优解之一。