538、把二叉搜索树转换为累加树

1、题目描述

要求：把二叉搜索树转换为累加树。

所谓累加树：以中序遍历序列举例更好理解，从后往前每个节点的值变成其后面的节点值之和。

如下图所示：

2、分析

2.1、记录val的累加值sum

class Solution {
public:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        //老样子，先写终止条件
        if(root == NULL) return NULL;
        //然后开始从后往前的中序遍历
        convertBST(root->right);
        sum += root->val;
        root->val = sum;
        cout << sum << ",";
        convertBST(root->left);
        return root;
    }
};

2.2、记录pre node

class Solution {
public:
    TreeNode* pre = NULL;
    TreeNode* convertBST(TreeNode* root) {
        //老样子，先写终止条件
        if(root == NULL) return NULL;
        //然后开始从后往前的中序遍历
        convertBST(root->right);
        if(pre == NULL){
            root->val = root->val;
        }else{
            root->val = root->val + pre->val;
        }
        pre = root;
        cout << root->val << ",";
        convertBST(root->left);
        return root;
    }
};

3、实现代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <math.h>

using namespace std;


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 == NULL) return NULL;
        //然后开始从后往前的中序遍历
        convertBST(root->right);
        sum += root->val;
        root->val = sum;
        cout << sum << ",";
        convertBST(root->left);
        return root;
    }
};
*/

class Solution {
public:
    TreeNode* pre = NULL;
    TreeNode* convertBST(TreeNode* root) {
        //老样子，先写终止条件
        if(root == NULL) return NULL;
        //然后开始从后往前的中序遍历
        convertBST(root->right);
        if(pre == NULL){
            root->val = root->val;
        }else{
            root->val = root->val + pre->val;
        }
        pre = root;
        cout << root->val << ",";
        convertBST(root->left);
        return root;
    }
};


int main()
{
    Solution s1;
    TreeNode node4(0);
    TreeNode node6(5);
    TreeNode node8(3);
    TreeNode node9(8);
    TreeNode *pnode5 = new TreeNode(2, NULL, &node8);
    TreeNode *pnode7 = new TreeNode(7, NULL, &node9);
    TreeNode *pnode2 = new TreeNode(1, &node4, pnode5);
    TreeNode *pnode3 = new TreeNode(6, &node6, pnode7);
    TreeNode *pnode1 = new TreeNode(4, pnode2, pnode3);
    s1.convertBST(pnode1);
}