c++ solution beats 100%


  • 14
    X

    The solution is the modification of inorder travel. Namely, travel right subtree, change the root value, and travel left subtree.

    class Solution {
    private:
        int cur_sum = 0;
    public:
        void travel(TreeNode* root){
            if (!root) return;
            if (root->right) travel(root->right);
            
            root->val = (cur_sum += root->val);
            if (root->left) travel(root->left);
        }
        TreeNode* convertBST(TreeNode* root) {
            travel(root);
            return root;
        }
    };
    

  • 0

    brilliant solution!


  • 1
    C

    I shaved another couple of ms off by testing for root non-NULL in convertBST(), so there is no need to test it at all in travel(). (36 ms for the 212 runs, with a favorable wind) (Last night mid-contest I got all tangled up in adding the running sum twice, or not at all. With a good night's sleep and a fresh lookI got as far as a Right-to-Left Depth-First Search, using temporary values to hold the old value of either root->val or sum. The basic compiler doesn't optimize it unless it is phrased as you did

    ...
        root->val = (cur_sum += root->val);
    ...
    

    So it looks like:

    TreeNode* convertBST(TreeNode* root) {
            if (root)
            {
                travel(root);
            }
            return root;
    }
    

  • 1
    L

    Here is a solution without defining helper function. :)

    class Solution {
    public:
        int sum = 0;
        
        TreeNode* convertBST(TreeNode* root) {
            if (root) {
                convertBST(root->right);
                root->val += sum;
                sum = root->val;
                convertBST(root->left);
            }
            return root;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.