Leetcode 99. Recover Binary Search Tree O(1)

红太狼 2022-06-09 06:21 138阅读 0赞

题目中要求用constant space去结题，那就不能使用中序遍历类似的递归写法，因为这些的空间复杂度平均水平是O(logN)。那么只有使用一种（新的）遍历算法[Morris Traversal][]。

然后结合中序遍历的结题思路，左子树的最大值要小于根节点和右子树的值。

/** * 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 {
    public:
        void recoverTree(TreeNode* root) {
            TreeNode* cur = root,* pre = nullptr;
            while(cur)
            {
                if(cur->left == nullptr)
                {
                    iserror(cur);
                    last = cur;
                    //printf("%d\n", last->val);
                    cur = cur->right;
                }
                else
                {
                    pre = cur->left;
                    while(pre->right != nullptr && pre->right != cur)
                        pre = pre->right;
    
                    if(pre->right == nullptr)
                    {
                        pre->right = cur;
                        cur = cur->left;
                    }
                    else
                    {
                        pre->right = nullptr;
                        iserror(cur);
                        last = cur;
                        //printf("%d\n", last->val);
                        cur = cur->right;
                    }
                }
            }
            swap(node1->val, node2->val);
        }
    private:
        TreeNode* node1 = nullptr;
        TreeNode* node2 = nullptr;
        TreeNode* last = new TreeNode(INT_MIN);
        void iserror(TreeNode* cur)
        {
            //printf("%d %d\n", last->val, cur->val);
            if(!node1 && last->val > cur->val)   node1 = last;
            if( node1 && last->val > cur->val)   node2 = cur;
        }
    };

[Morris Traversal]: http://blog.csdn.net/u013007900/article/details/77663733