189.二叉树：把二叉搜索树转换为累加树（力扣）

代码解决

/*** 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:// pre 用于保存累加和int pre = 0;// 中序遍历函数，按照右-根-左的顺序遍历void traversal(TreeNode* root){if (root == nullptr) return;// 遍历右子树traversal(root->right);// 更新节点值root->val += pre;// 更新累加和pre = root->val;// 遍历左子树traversal(root->left);}// 将BST转换成累加树的函数TreeNode* convertBST(TreeNode* root) {traversal(root);return root;}
};

代码使用了递归的方法。主要思路是使用中序遍历的方式遍历二叉搜索树，但改变遍历的顺序，即先遍历右子树，然后访问当前节点，最后遍历左子树。在遍历过程中，每次访问一个节点时，将该节点的值加上其所有右子节点的值。

这里简要解释一下代码的工作流程：

1. 定义一个全局变量 pre 用于记录累加和，初始值为0。
2. 定义一个辅助函数 traversal，它接受当前节点作为参数。
3. 如果当前节点为空，则返回。
4. 首先遍历右子树。
5. 更新当前节点的值为其自身值加上 pre。
6. 更新 pre 为当前节点的值。
7. 然后遍历左子树。
8. 在 convertBST 函数中，调用 traversal 函数开始中序遍历，并返回转换后的根节点。

这个算法的时间复杂度是 O(n)，其中 n 是树中节点的数量。空间复杂度也是 O(n)，因为需要存储递归调用的栈。