99. 恢复二叉搜索树 - 力扣（LeetCode）

相关算法：二叉树前序遍历（144）、中序遍历（94）、后序遍历（145）-CSDN博客

官方解法：

/*** 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://non reursivevoid recoverTree(TreeNode* root) {stack<TreeNode*> stk;TreeNode* x = nullptr;TreeNode* y = nullptr;TreeNode* predecessor = nullptr;TreeNode * tmp = nullptr;tmp = root;while (tmp != nullptr || !stk.empty()) {while (tmp != nullptr) {stk.push(tmp);tmp = tmp->left;}tmp = stk.top();stk.pop();//对于只有1个逆序的情况，这个if条件满足一次；如果有2个逆序的情况，这个if条件满足两次if (predecessor != nullptr && predecessor->val > tmp->val) {y = tmp;if (x == nullptr) {x = predecessor;}else{break;}}predecessor = tmp;tmp = tmp->right;}swap(x->val, y->val);}
};

总结：

算法过程：对于二叉搜索树，它的中序遍历是val递增的序列。对于交换了其中的两个val， 存在2种情况，举一个例子，例如{1, 2, 3, 4, 5, 6, 7, 8}，a.交换相邻的两个数字，譬如交换2,3，则序列为{1, 3, 2, 4, 5, 6, 7, 8}，存在1个逆序关系（3->2） ；b.交换不相邻的两个数字，譬如交换2,5，则序列为{1, 5, 3, 4, 2, 6, 7, 8}，则存在两个逆序关系（5->3，4->2 ）。在代码中predecessor代表遍历的当前节点的前一个节点。x记录第一个逆序的predecessor。

计算的时间复杂度O(N)，空间复杂度O(N)。