【LeetCode-538 | 把二叉搜索树转换为累加树】

题目.jpg 题目.jpg 题目.jpg

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <utility>
#include <algorithm>

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 {
private:
    int pre = 0;  // 用来保存node节点的前一个节点的数值
public:
    /*
        解题思想：使用右、根、左的遍历顺序，然后按顺序累加遍历到的节点
    */
        // 1.确定入参及返回值
    void Traversal(TreeNode* node) {
        // 2.确定递归终止条件
        if(node == nullptr) return ;
        // 3.确定单层递归逻辑
        Traversal(node->right);  // 右
        
        node->val += pre;   // 根
        pre = node->val;

        Traversal(node->left);   // 左
    }
        
    TreeNode* convertBST(TreeNode* root) {
        Traversal(root);
        return root;
    }
};