leetcode99.恢复二叉搜索树/中序遍历

题目&＃xff1a;二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下&＃xff0c;恢复这棵树。

示例 1:

输入: [1,3,null,null,2]1/3\2输出: [3,1,null,null,2]3/1\2


示例 2:

输入: [3,1,4,null,null,2]3/ \
1 4/2输出: [2,1,4,null,null,3]2/ \
1 4/3


进阶:

• 使用 O(n) 空间复杂度的解法很容易实现。
• 你能想出一个只使用常数空间的解决方案吗&＃xff1f;

来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;
链接&＃xff1a;https://leetcode-cn.com/problems/recover-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权&＃xff0c;非商业转载请注明出处。

基本思想1&＃xff1a;中序遍历

二叉搜索树中序遍历的结果一定是升序序列&＃xff0c;那么在该题中中序遍历的序列在交换两个元素后&＃xff0c;成为升序序列。

• 首先&＃xff0c;对二叉树进行中序遍历&＃xff0c;并保存中序遍历的结果序列
• 寻找结果序列中第一个逆序的元素前面的元素pre
• 从元素pre一直往后寻找&＃xff0c;当找到一个大于该元素的元素temp时&＃xff0c;temp前面的元素post就是需要交换的元素
• 将pre和post这两个元素进行交换

空间复杂度为O&＃xff08;n&＃xff09;的写法
定义一个数组保存中序遍历的顺序

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vector<TreeNode*> vec;void recoverTree(TreeNode* root) {inorder(root);int pre &＃61; 0, i;for(i &＃61; 1; i < vec.size(); &＃43;&＃43;i){if(vec[i]->val > vec[pre]->val)&＃43;&＃43;pre;elsebreak;}for(; i < vec.size(); &＃43;&＃43;i){if(vec[i]->val > vec[pre]-> val)break;}--i;int t &＃61; vec[i]->val;vec[i]->val &＃61; vec[pre]->val;vec[pre]->val &＃61; t;}void inorder(TreeNode* root){if(root &＃61;&＃61; NULL)return;inorder(root->left);vec.push_back(root);inorder(root->right);}
};


空间复杂度为O&＃xff08;1&＃xff09;的写法&＃xff1a;
定义两个变量来保存逆序的两个节点

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:void recoverTree(TreeNode* root) {TreeNode* pre1 &＃61; NULL, *pre2 &＃61; NULL;inorder(root, pre1, pre2);int t &＃61; pre1->val;pre1->val &＃61; pre2->val;pre2->val &＃61; t;}void inorder(TreeNode* root, TreeNode* &pre1, TreeNode* &pre2){if(root &＃61;&＃61; NULL)return;inorder(root->left, pre1, pre2);if(pre1 &＃61;&＃61; NULL){//root是根节点的情况pre1 &＃61; root;}else{if(root->val > pre1->val && (!pre2 || root->val < pre2->val)){pre1 &＃61; root;}else if(pre2 &＃61;&＃61; NULL){//此时找到了第一个需要交换的节点&＃xff0c;保存在pre2中pre2 &＃61; pre1;pre1 &＃61; root;}if((root->val < pre1->val) && (pre2) && (pre2->val > root->val)){//此时找到了第二个需要交换的节点保存在pre1中pre1 &＃61; root;}}inorder(root->right, pre1, pre2);}
};