恢复二叉搜索树

对二叉搜索树进行中序遍历，用数组保存结点，用另一个数组保存结点的值，然后找到值错误的两个结点，然后直接交换值就行

 class Solution {
public:
    void recoverTree(TreeNode* root) {
        vector<int> vals;
        vector<TreeNode*> nodes;
        stack<TreeNode*> stk;
        TreeNode* curr = root;
        // 非递归中序遍历
        while (curr != nullptr || !stk.empty()) {
            while (curr != nullptr) {
                stk.push(curr);
                curr = curr->left;
            }
            curr = stk.top();
            stk.pop();
            vals.push_back(curr->val);
            nodes.push_back(curr); 
            curr = curr->right;
        }
       // 找第一个逆序位置i
        int i = 0, j = vals.size() - 1;
        while (i < vals.size() - 1 && vals[i] < vals[i+1]) i++;
        // 找最后一个逆序位置j
        while (j > 0 && vals[j] > vals[j-1]) j--;
        // 交换两个异常节点的数值
        swap(nodes[i]->val, nodes[j]->val);
    }
};

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