99.Recover Binary Search Tree¶

99.Recover Binary Search Tree¶

Tags: Tree Hard

Links: https://leetcode.com/problems/recover-binary-search-tree/

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2:

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?

/**
 * 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) {
        if (!root) return;

        vector<TreeNode *> seq;
        vector<int> res;

        inorder(root, seq, res);
        sort(res.begin(), res.end());
        for (size_t i = 0; i < seq.size(); ++i)
            seq[i] -> val = res[i];
    }

    void inorder(TreeNode * root, vector<TreeNode *> & seq, vector<int> & res) {
        if (root -> left) inorder(root -> left, seq, res);
        seq.push_back(root);
        res.push_back(root -> val);
        if (root -> right) inorder(root -> right, seq, res);
    }
};

题目要求里面写空间复杂度要求是常数，并且提示了O(n)的写法，如果我们按中序遍历，那么如果二叉树是正确的，那么它必定是升序的，所以可以先中序遍历，把结果保存在一个数组里面，排序恢复即可，最后赋值给节点即可。

如果想到了中序遍历，那么在常数空间复杂度的提示下，就比较容易想到线索二叉树，这里还需要注意，因为我们还采用了一个数组来存储遍历的结果，还需要把它优化成常数空间。中序遍历结果必然是升序有序的，那么出现错误一定会出现逆序，出现逆序会有两种情况：

1 2 4 3 5 6 //错误的位置相连
1 5 3 4 2 6 //错误的位置不相连，交换的是第一个逆序对的第一个数，和第二个逆序对的第二个数

所以可以考虑用每次用两个指针来探测找出逆序对，那么找出一个逆序对应该用一个额外的指针来存储第一个错误的位置，然后两个指针继续探测找出第二个位置。所以可以只用三个指针，以此代替数组完成优化。

/**
 * 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) {
        if (!root) return;

        TreeNode *first = nullptr, *second = nullptr, *pre = nullptr;
        while (root) {
            if (root -> left == nullptr) {
                if (pre && pre -> val > root -> val) {
                    if (first == nullptr){
                        first = pre;
                        second = root;
                    } 
                    else second = root;
                }
                pre = root;
                root = root -> right;
            }
            else {
                TreeNode *p = root -> left;
                while (p -> right != nullptr && p -> right != root)
                    p = p -> right;

                if (p -> right == nullptr) {
                    p -> right = root;
                    root = root -> left;
                }
                else {
                    if (pre && pre -> val > root -> val) {
                        if (first == nullptr) {
                            first = pre;
                            second = root;
                        } 
                        else second = root;
                    }
                    p -> right = nullptr;
                    pre = root;
                    root = root -> right;
                }
            }
        }
        std::swap(first -> val, second -> val);
    }
};

这里比较容易想到如果first != nullptr然后second = root代表已经找到两个错误的节点，可以剪枝，但是要注意我们要恢复二叉树，如果这里直接break，那么二叉树本身也就改变了。