Simple recursive C++ solution, an iterative Morris solution is also enclosed


  • 0

    using reference to pointer instead of pointer to pointer


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

  • 0

    An iterative solution is enclosed here, accepted as best

    class Solution {
    public:
        void recoverTree(struct TreeNode* root)
        {
            struct TreeNode *pre=NULL, *first=NULL, *second=NULL;
            struct TreeNode *t = NULL;
            while(root)
            {
                if(root->left)
                {
                    t = root->left;
                    while(t->right && t->right!=root) t = t->right;
                    if(t->right)
                    {
                        if(pre && pre->val > root->val)
                        {
                            if(!first)
                            {
                                first = pre;
                                second = root;
                            }
                            else second = root;
                        }
                        pre = root;
                        t->right = NULL;
                        root = root->right;
                    }
                    else
                    {
                        t->right = root;
                        root = root->left;
                    }
                }
                else
                {
                    if(pre && pre->val > root->val)
                    {
                        if(!first) first=pre, second=root;
                        else second = root;
                    }
                    pre = root;
                    root = root->right;
                }
            }
            if(first && second)
            {
                first->val += second->val;
                second->val = first->val-second->val;
                first->val -= second->val;
            }
        }
    };

  • 0

    Another version of the iterative - also Morris Traversal


    class Solution {
    public:
        void recoverTree(struct TreeNode* root)
        {
            TreeNode *pre=NULL, *first=NULL, *second=NULL;
            while(root)
            {
                if(!root->left)
                {
                    if(pre && pre->val > root->val)
                    {
                        if(!first) first = pre;
                        second = root;
                    }
                    pre = root;
                    root = root->right;
                }
                else
                {
                    TreeNode *t = root->left;
                    while(t->right && t->right!=root) t = t->right;
                    if(!t->right)
                    {
                        t->right = root;
                        root = root->left;
                    }
                    else
                    {
                        t->right = NULL;
                        if(pre && pre->val > root->val)
                        {
                            if(!first) first = pre;
                            second = root;
                        }
                        pre = root;
                        root = root->right;
                    }
                }
            }
            if(first && second)
                swap(first->val, second->val);
        }
    };

  • 0

    recursive version becomes more clean now.


Log in to reply
 

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