今日算法（二叉搜索树）

题目描述

给定一棵二叉搜索树（BST）的根节点root，树中节点值各不相同。要求将其转换为累加树（Greater Sum Tree），规则如下：

• 每个节点的新值 = 原节点值 + 所有比它大的节点值的总和
• 二叉搜索树的性质：
  • 左子树所有节点值 < 根节点值
  • 右子树所有节点值 > 根节点值
  • 中序遍历结果为升序序列

核心思路：逆中序遍历 + 累加

要实现累加树，关键是从大到小遍历所有节点，边遍历边累加，再更新当前节点的值。

核心逻辑

二叉搜索树的 ** 中序遍历（左 - 根 - 右）是升序，那么逆中序遍历（右 - 根 - 左）** 就是降序。

• 我们按降序遍历所有节点，用一个变量sum记录遍历过的节点值总和
• 每次访问一个节点时，先更新sum（加上当前节点值），再把sum赋值给当前节点
• 这样就能保证每个节点的值 = 原节点值 + 所有比它大的节点值的和

完整代码实现（C++）

cpp

/** * 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

遍历过程

1. 访问节点8
   • sum += 8→sum = 8
   • root->val = 8（节点值更新为 8）
2. 访问节点7
   • sum += 7→sum = 15
   • root->val = 15（节点值更新为 15）
3. 访问节点6
   • sum += 6→sum = 21
   • root->val = 21（节点值更新为 21）
4. 访问节点5
   • sum += 5→sum = 26
   • root->val = 26（节点值更新为 26）
5. 访问节点4
   • sum += 4→sum = 30
   • root->val = 30（节点值更新为 30）
6. 访问节点3
   • sum += 3→sum = 33
   • root->val = 33（节点值更新为 33）
7. 访问节点2
   • sum += 2→sum = 35
   • root->val = 35（节点值更新为 35）
8. 访问节点1
   • sum += 1→sum = 36
   • root->val = 36（节点值更新为 36）
9. 访问节点0
   • sum += 0→sum = 36
   • root->val = 36（节点值更新为 36）

最终结果

所有节点值更新为：[30, 36, 21, 36, 35, 26, 15, null, null, null, 33, null, null, null, 8]，和示例输出完全一致。

关键细节与易错点

1. 逆中序遍历的顺序必须严格按照右子树 → 根节点 → 左子树的顺序遍历，这样才能保证先访问所有比当前节点大的节点，再更新当前节点的值。

2. 累加和变量sum的作用sum是一个全局变量（或通过引用传递的变量），记录所有已经访问过的节点值的总和，每次更新节点值时，直接赋值sum即可，无需重复计算。

3. 空节点的处理当root == nullptr时，直接返回，不做任何操作，这是递归的终止条件。

4. 节点值的修改顺序必须先更新sum，再修改root->val，否则会导致节点值更新错误。

复杂度分析

• 时间复杂度：\(O(n)\)，其中 n 为树的节点数。每个节点只会被访问一次。
• 空间复杂度：\(O(h)\)，其中 h 为树的高度。递归调用栈的深度等于树的高度，最坏情况下（树退化为链表）为 \(O(n)\)。

拓展：迭代版实现（可选）

如果不想使用递归，可以用栈模拟逆中序遍历：

cpp

class Solution { public: TreeNode* convertBST(TreeNode* root) { int sum = 0; stack<TreeNode*> 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; } };

总结

将二叉搜索树转换为累加树的核心，就是利用逆中序遍历的降序特性，边遍历边累加更新节点值。这种方法无需额外空间，仅通过一次遍历就能完成转换，时间复杂度为线性，是最优解之一。