convert-bst-to-greater-tree

Convert BST to Greater Tree – LeetCode 538

Problem

Description

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Answer

Original

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    long cache = 0;
public:
    TreeNode* convertBST(TreeNode* root) {
        if(root){
            if(root->right) convertBST(root->right);
            cache += root->val;
            root->val = cache;
            if(root->left) convertBST(root->left);
        }
        return root;
    }
};

思路

逆向的中序便利累加。时间复杂度$O(n)$，空间复杂度$O(log(n))$。
耗时$24$ ms，排名$2.48\%$

Better

思路

还没看到更好的思路。