首页 > 代码库 > leetcode - Recover Binary Search Tree
leetcode - Recover Binary Search Tree
题目：Recover Binary Search Tree
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?
这道题的意思是本来有一颗BST，但是不小心把其中两个节点互换了，现在需要把这两个节点换回来，或者交换这两个节点的值也行，关键在于找到这两个互换节点
个人思路：
1、创建一个vector<TreeNode *> A，保存中序遍历的所有节点，由于原BST有两个节点互换了，那么该中序遍历的结果并不是递增的
2、再创建一个vector<TreeNode *> B，并用A的元素初始化B，然后为B排序，此时的B是递增顺序的（也即对调了互换节点的指针），遍历比较这两个vector的元素，当发现A的元素不等于B的元素时，表明两个不相等的元素就是那两个互换节点，找到这两个互换节点后，交换它俩的值即可
代码：
1 #include <stddef.h> 2 #include <vector> 3 #include <algorithm> 4 5 using namespace std; 6 /* 7 struct TreeNode 8 { 9 int val;10 TreeNode *left;11 TreeNode *right;12 TreeNode(int x) : val(x), left(NULL), right(NULL) {}13 };14 */15 class Solution16 {17 public:18 void recoverTree(TreeNode *root)19 {20 vector<TreeNode *> inorderRaw;21 inorder(root, inorderRaw);22 vector<TreeNode *> inorderSorted(inorderRaw);23 sort(inorderSorted.begin(), inorderSorted.end(), Solution::cmp);24 vector<TreeNode *>::iterator raw = inorderRaw.begin();25 vector<TreeNode *>::iterator sorted = inorderSorted.begin();26 27 while (true)28 {29 if ((*raw)->val != (*sorted)->val)30 {31 break;32 }33 ++raw;34 ++sorted;35 }36 int tmp = (*raw)->val;37 (*raw)->val = (*sorted)->val;38 (*sorted)->val = tmp;39 }40 static bool cmp(const TreeNode *first, const TreeNode *second)41 {42 return first->val <= second->val;43 }44 private:45 void inorder(TreeNode *root, vector<TreeNode *> &inorderRaw)46 {47 if (!root)48 {49 return;50 }51 inorder(root->left, inorderRaw);52 inorderRaw.push_back(root);53 inorder(root->right, inorderRaw);54 }55 };56 /*57 int main()58 {59 return 0;60 }61 */
题目要求仅使用常数空间，上面的算法不和要求，上网看了几篇文章，找到了符合题意的算法（一开始我也是这么想的，但后来想岔了），链接：http://blog.163.com/ya_mzy/blog/static/19959325520137153340725/
思路：
1、这里我们先举个例子来说明，比如一个正常的BST中序遍历应该是递增的，如1234567，现在互换了两个节点3和6，变成1264537
2、那么，有什么特点呢？当中序遍历时，会有一个节点比后一个节点大，一个节点比前一个节点小，我们就要找到这两个节点，通过预设一个pre指针用于记录中序遍历的前一个节点即可，当这两个互换的节点相邻时，如1243567，仅会有一次当前节点小于前一节点的情况（一般会出现两次，第一次是前一节点，第二次是当前节点），这时这两个节点便是互换节点
代码：
1 #include <stddef.h> 2 3 struct TreeNode 4 { 5 int val; 6 TreeNode *left; 7 TreeNode *right; 8 TreeNode(int x) : val(x), left(NULL), right(NULL) {} 9 };10 11 class Solution12 {13 public:14 void recoverTree(TreeNode *root)15 {16 TreeNode *swappedElement1 = NULL;17 TreeNode *swappedElement2 = NULL;18 TreeNode *pre = NULL;19 20 findSwappedElements(root, pre, swappedElement1, swappedElement2);21 22 int tmp = swappedElement1->val;23 swappedElement1->val = swappedElement2->val;24 swappedElement2->val = tmp;25 }26 private:27 void findSwappedElements(TreeNode *root, TreeNode *&pre, TreeNode *&swappedElement1, TreeNode *&swappedElement2)28 {29 if (!root)30 {31 return;32 }33 34 findSwappedElements(root->left, pre, swappedElement1, swappedElement2);35 36 if (pre && root->val < pre->val)37 {38 if (!swappedElement1)39 {40 swappedElement1 = pre;41 swappedElement2 = root;42 }43 else44 {45 swappedElement2 = root;46 }47 }48 49 pre = root;50 51 findSwappedElements(root->right, pre, swappedElement1, swappedElement2);52 }53 };54 55 int main()56 {57 return 0;58 }