99. Recover Binary Search Tree (Hard)

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

Recover the tree without changing its structure.

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

Solution 1: DFS, Iteration 25ms

这道题要求我们复原一个二叉搜索树，说是其中有两个的顺序被调换了，题目要求上说O(n)的解法很直观，这种解法需要用到递归，用中序遍历树，并将所有节点存到一个一维向量中，把所有节点值存到另一个一维向量中，然后对存节点值的一维向量排序，在将排好的数组按顺序赋给节点。这种最一般的解法可针对任意个数目的节点错乱的情况，这里先贴上此种解法：

/**
 * 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) {
        stack<TreeNode*> s;
        TreeNode* prev = new TreeNode(INT_MIN);
        TreeNode* n1 = NULL, *n2 = NULL;
        while (root || !s.empty()) {
            while (root) {
                s.push(root);
                root = root->left;
            }
            if (!s.empty()) {
                root = s.top(); s.pop();
                if (!n1 && root->val < prev->val) n1 = prev;
                if (n1 && root->val < prev->val)  n2 = root;

                prev = root;
                root = root->right;
            }
        }
        swap(n1->val, n2->val);
    }
};

Solution 2:

class Solution {
    void inorder(TreeNode* root) {
        if (!root) return;
        inorder(root->left);
        if (!n1 && root->val < prev->val) n1 = prev;
        if (n1 && root->val < prev->val) n2 = root;
        prev = root;
        inorder(root->right);
    }
public:
    void recoverTree(TreeNode* root) {
        inorder(root);
        swap(n1->val, n2->val);
    }
private:
    TreeNode* n1 = NULL, *n2 = NULL;
    TreeNode* prev = new TreeNode(INT_MIN);
};