澳门特别行政区网站建设_网站建设公司_云服务器_seo优化

输入：二叉搜索树根节点root（节点值各不相同）。

要求：将其转换为累加树（Greater Sum Tree）：
每个节点的新值 = 原树中所有大于等于该节点值的节点值之和。

输出：转换后的树根节点TreeNode*（原地修改后返回root）。

思路：

BST 的中序遍历（左-根-右）是递增序列。
那我们如果想做“后缀和”（从大到小累加），就把遍历方向反过来：

逆向中序遍历：右 -> 根 -> 左
访问顺序从大到小，维护一个滚动累加sum。

遍历到某个节点时：

1. 先走右子树（更大的值先处理）
2. sum += node->val
3. node->val = sum（把当前节点改成“>= 自己的总和”）
4. 再走左子树

补充：
也能用“两次正序中序”做：第一次中序存有序数组并做后缀和映射，第二次再中序回填。
但那是 O(N) 额外空间；本题一趟逆向中序就能原地搞定。

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(H)（递归栈，H 为树高）

classSolution{public:TreeNode*convertBST(TreeNode*root){sum=0;reverseInorder(root);returnroot;}private:intsum;voidreverseInorder(TreeNode*node){if(node==nullptr)return;reverseInorder(node->right);sum+=node->val;node->val=sum;reverseInorder(node->left);}};