# 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?

Morris Traversal中序遍历的原理比较简单：

+ 如果当前节点的左孩子为空，则输出当前节点并将其有孩子作为当前节点。
+ 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点，也就是当前节点左子树的最右边的那个节点。
+ 如果前驱节点的右孩子为空，则将它的右孩子设置为当前节点，当前节点更新为其左孩子。
+ 如果前驱节点的右孩子为当前节点，则将前驱节点的右孩子设为空，输出当前节点，当前节点更新为其右孩子。

```c++
class Solution {
public:
void recoverTree(TreeNode *root) {
TreeNode* cur = 0;
TreeNode* pre = 0;
TreeNode* p1 = 0;
TreeNode* p2 = 0;
TreeNode* preCur = 0;

bool found = false;

if(!root) {
return;
}

cur = root;
while(cur) {
if(!cur->left) {
//记录p1和p2
if(preCur && preCur->val > cur->val) {
if(!found) {
p1 = preCur;
found = true;
}
p2 = cur;
}

preCur = cur;
cur = cur->right;
} else {
pre = cur->left;
while(pre->right && pre->right != cur) {
pre = pre->right;
}

if(!pre->right) {
pre->right = cur;
cur = cur->left;
} else {
//记录p1和p2
if(preCur->val > cur->val) {
if(!found) {
p1 = preCur;
found = true;
}
p2 = cur;
}
preCur = cur;
pre->right = NULL;
cur = cur->right;
}
}
}

if(p1 && p2) {
int t = p1->val;
p1->val = p2->val;
p2->val = t;
}
}
};
```
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://coderhelper.top/book/leetcode/34.html", "fetch_time": 1575848024000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2019-51/segments/1575540515344.59/warc/CC-MAIN-20191208230118-20191209014118-00126.warc.gz", "warc_record_offset": 35560367, "warc_record_length": 4722, "token_count": 482, "char_count": 1252, "score": 3.546875, "int_score": 4, "crawl": "CC-MAIN-2019-51", "snapshot_type": "latest", "language": "en", "language_score": 0.2731032371520996, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00048-of-00064.parquet"}