99. 恢复二叉搜索树
给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
示例 1：
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。示例 2：
输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。提示：
- 树上节点的数目在范围
[2, 1000]内 -231 <= Node.val <= 231 - 1
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？
题解
O(1)可以通过Morris遍历实现。前一个题力扣 98. 验证二叉搜索树 [递归;迭代;Morris]可以帮助理解这个题。
未被错误交换前，通过中序遍历得到的数组，是升序的，如1,2,3,4,5，如果2和5交换，中序遍历会得到1,5,3,4,2。在遍历时，会发现两个不满足有效二叉树的情况：5,3和4,2。第一次不满足情况是5,3，当遍历到当前节点3时，前一个节点5>3，第二次是遍历到当前节点2时，前一个节点4>2，则第一次不满足的情况出现时，我们需要记录前一个节点5，当第二次情况出现时，记录当前节点2，遍历完之后交换记录的5和2，即可。
查看代码
/**
* 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:
void recoverTree(TreeNode* root) {
TreeNode* node=nullptr;//中序遍历条件下：当前节点的前一个节点
TreeNode* error1=nullptr;//第一个错误的节点
TreeNode* error2=nullptr;//第二个
while (root != NULL)
{
if (root->left == NULL)
{
// cout << root->val << " ";//输出当前节点
if(node&&node->val>root->val)//前一个节点存在，且不满足升序，需要记录错误节点
{
if(!error1)//第一次
error1=node;
error2=root;//第二次
}
node=root;
root = root->right;
}
else
{
// 找当前节点的前趋结点
TreeNode* predecessor = root->left;
while (predecessor->right != NULL
&& predecessor->right != root)
{
predecessor = predecessor->right;
}
// 使当前节点成为inorder的前序节点的右侧子节点
if (predecessor->right == NULL)
{
predecessor->right = root;
root = root->left;
}
//复原之前的修改
else
{
predecessor->right = NULL;
// cout << root->val << " ";//输出当前节点
if(node&&node->val>root->val)//前一个节点存在，且不满足升序
{
if(!error1)
error1=node;
error2=root;
}
node=root;
root = root->right;
}
}
}
if(error1){//进行交换
int t=error1->val;
error1->val=error2->val;
error2->val=t;
}
}
};标签：力扣,right,TreeNode,val,99,Morris,root,节点,left From： https://www.cnblogs.com/fudanxi/p/16953005.html