【二叉树】把二叉搜索树转换为累加树

解题思路：递归解决，右中左遍历

递归结束条件：传入结点为NULL，返回NULL

创建一个全局变量sum来记录当前结点总值

1.先递归进入右子树，改变右孩子的值。

2.将当前结点的值变为root->val + sum;

3.进入左孩子。将结点的值变为root->val sum

4.返回当前结点

struct TreeNode* convertBST2(struct TreeNode* root, int* sum) {
    if(!root)
        return NULL;
    convertBST2(root->right, sum);
    root->val += *sum;
    *sum = root->val;
    convertBST2(root->left, sum);
    return root;
}

struct TreeNode* convertBST(struct TreeNode* root) {
    int sum = 0;
    return convertBST2(root, &sum);
}

解题思路：迭代右中左遍历二叉树，用栈辅助

设立一个全局变量sum来记录上一个结点的值

1.将结点current设置为根结点进行迭代。

2.当current结点存在或者栈中不为空时：

a.若current结点存在，将其入栈，使current=current->right

b.若current结点不存在，取出栈顶元素。使current->val += sum。然后将current=current->left

3.最后在函数中返回root

struct TreeNode* convertBST(struct TreeNode* root){
    int sum = 0;
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 10000);
    int stack_top = 0;
    
    struct TreeNode* current = root;
    while(current || stack_top > 0) {
        if(current) {
            stack[stack_top++] = current;
            current = current->right;
        } else {
            current = stack[--stack_top];
            current->val += sum;
            sum = current->val;
            current = current->left;
        }
    }
    return root;
}