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

Problem: 538. 把二叉搜索树转换为累加树

思路

根据实例可以看出,是根据右->中->左的顺序累加的,我们只需要得到前面一个节点,与当前节点相加即可,并且直接改变原值,进行累计。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
public:
    TreeNode* preNode;
    TreeNode* convertBST(TreeNode* root) {
        if(root == nullptr) return nullptr;
        convertBST(root->right);
        if(preNode != nullptr)  root->val = preNode->val + root->val;
        preNode = root;
        convertBST(root->left);
        return root;
    }
};