本文共 487 字，大约阅读时间需要 1 分钟。

题目：BST中，某2个节点交换了位置，求出正确的BST。

最简单的解法：O（n）的空间复杂度，两次中序遍历。

class Solution {public:    vector
   
    v;    int index = 0;    void inorder(TreeNode* root,int ok){         if(!root) return ;         inorder(root->left,ok);         if(ok)              root->val = v[index],index++;         else            v.push_back(root->val);         inorder(root->right,ok);    }    void recoverTree(TreeNode* root) {         inorder(root,0);         sort(v.begin(),v.end());         inorder(root,1);    }};
   

转载地址：http://jirai.baihongyu.com/