99. 恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

 

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。  

提示：

树上节点的数目在范围 [2, 1000] 内
-231 <= Node.val <= 231 - 1  

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

---

中序遍历

1. 先中序遍历拿到遍历结果值
2. 然后找到异常的2个数。分是否相邻两种情况
3. 遍历二叉树修复这两个数

时间复杂度: O(n)
空间复杂度：O(n)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    void inOrder(TreeNode* root, vector<int> &nums) {
        if (root == nullptr) return;
        inOrder(root->left, nums);
        nums.emplace_back(root->val);
        inOrder(root->right, nums);
    }

    // 如果交换的是两个相邻的数，则只能找到一个异常点；
    // 如果交换的不是相邻的数，则能找到2个异常点
    pair<int, int> findTwo(const vector<int> &nums) {
        int index1 = -1, index2 = -1;
        for (int i = 0; i < nums.size()-1; i++) {
            if (nums[i+1] < nums[i]) {
                index2 = i+1;
                // index1再次出现 说明找到了第二个异常的数
                if (index1 == -1) {
                    index1 = i;
                }else{
                    break;
                }
            }
        }
        return {nums[index1], nums[index2]};
    }

    void recover(TreeNode* root, int x, int y, int count) {
        if (root == nullptr) return;
        if (root->val == x || root->val == y) {
            root->val = root->val == x ? y : x;
            if (--count == 0) return;
        }
        recover(root->left, x, y, count);
        recover(root->right, x, y, count);
    }
public:
    void recoverTree(TreeNode* root) {
        vector<int> treeNums;
        inOrder(root, treeNums);
        auto two = findTwo(treeNums);
        recover(root, two.first, two.second, 2);
    }
};

其实没必要真正返回一个数组存储中序遍历的结果，可以在中序遍历的过程中直接找到异常的数，然后交换。

一次遍历二叉树得到，时间复杂度为O(n)
空间复杂度主要来自于递归调用深度，为二叉树高度，最坏情况下为单链表，O(n)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    // 注意，指针也需要是引用类型
    void inOrder(TreeNode* root, TreeNode* &pre, TreeNode* &index1, TreeNode* &index2) {
        if (root == nullptr) return;
        inOrder(root->left, pre, index1, index2);
        if (pre != nullptr && pre->val > root->val) {
            index2 = root;
            if (index1 == nullptr){
                index1 = pre;
            }else{
                return;
            }
        }
        pre = root;
        inOrder(root->right, pre, index1, index2);
    }

public:
    void recoverTree(TreeNode* root) {
        TreeNode* pre = nullptr, *index1 = nullptr, *index2 = nullptr;
        inOrder(root, pre, index1, index2);
        if (index1 != nullptr && index2 != nullptr) {
            // cout << index1->val << " " << index2->val;
            int tmp = index1->val;
            index1->val = index2->val;
            index2->val = tmp;
        }
    }
};

Morris 中序遍历

TODO