恢复二叉搜索树
题目：
给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
示例：
思路：
嘶，递归递了加一起得两个点。
笔试的题是，交换了若干个相邻结点的，恢复成一颗二叉搜索树。估计就应该只能o(n)的空间复杂度了。
这个写了一个巧妙一些的方法。
因为这道题只存在，两个结点互相交换。最多造成两个顺序不一致的情况。即前驱结点的值大于当前结点的值。
这是一个中序遍历，因为中序遍历二叉搜索树可以得到一个递增序列。
当存在两个顺序不一致的时候，就都记录下来，交换下标0.3记录的结点的值。
当存在一个顺序不一致的时候，证明就两个相邻的交换了，换回来即可。
如图：
通过代码：
巧妙：
/** * 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 { public: vector<TreeNode*> v; TreeNode* prev = nullptr; void swap(int& a,int& b) { int t = a; a = b; b = t; } void order(TreeNode* root) { if(root == nullptr) { return; } order(root->left); if(prev != nullptr && prev->val >= root->val) { v.push_back(prev); v.push_back(root); } prev = root; order(root->right); } void recoverTree(TreeNode* root) { order(root); if(v.size() != 2) { // v.erase(v[0]); swap(v[0]->val,v[3]->val); } else swap(v[0]->val,v[1]->val); } };
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 { public: vector<int> v; int i = 0; TreeNode* prev = nullptr; void swap(int& a,int& b) { int t = a; a = b; b = t; } void order(TreeNode* root) { if(root == nullptr) { return; } order(root->left); v.push_back(root->val); order(root->right); } void reorder(TreeNode* root,int& i) { if(root == nullptr) { return; } reorder(root->left,i); if(root->val != v[i]) { root->val = v[i]; } i++; reorder(root->right,i); } void recoverTree(TreeNode* root) { order(root); sort(v.begin(), v.end()); reorder(root,i); } };
