[C++] Clear O(n)-time solution (reverse in-order)


  • 0

    Regular In-Order traversal visits nodes of BST from min-element up to max-element. By switching left and right recursions in the code of regular In-Order traversal, we get a similar traversal that visits BST nodes from max-element down to min-element. Now we just need to keep the sum of values visited so far in a passed-by-reference value (or a private member variable in class Solution). Then we can simply update each node's value when we visit it.

    TreeNode* convertBST(TreeNode *root) {
        int sum = 0;
        InOrderReverse(root, sum);
        return root;
    }
    
    void InOrderReverse(TreeNode *node, int &sum) {
        if (node) {
            InOrderReverse(node->right, sum);
            node->val = sum += node->val;
            InOrderReverse(node->left, sum);
        }
    }
    

Log in to reply
 

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