c++ in-order traversal solution


  • 0
    H

    Keep this property of BST in mind: The result of in-order traversal of a BST is an ascending array.

    class Solution {
    public:
        TreeNode* first = NULL;
        TreeNode* second = NULL;
        TreeNode* prev = new TreeNode(INT_MIN);
        void inOrderTraverse(TreeNode* root) {
            if(!root) return;
            inOrderTraverse(root->left);
            if(!first && prev->val > root->val) first = prev;
            if(first && prev->val > root->val) second = root;
            prev = root;
            inOrderTraverse(root->right);
        }
        void recoverTree(TreeNode* root) {
            inOrderTraverse(root);
            swap(first->val, second->val);
        }
    };
    

Log in to reply
 

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