算法描述：
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Example 1:
Input: [1,3,null,null,2] 1 / 3 2 Output: [3,1,null,null,2] 3 / 1 2
Example 2:
Input: [3,1,4,null,null,2] 3 / 1 4 / 2 Output: [2,1,4,null,null,3] 2 / 1 4 / 3
Follow up:
解题思路：二叉搜索树的中序遍历是从小到大的顺序。所以，中序遍历该树，并将破坏顺序的两个节点值交换。
void recoverTree(TreeNode* root) { if(root == nullptr ) return; TreeNode* first = nullptr; TreeNode* second = nullptr; TreeNode* prev = nullptr; stack<TreeNode*> stk; TreeNode* cur = root; while(cur!=nullptr || !stk.empty()){ while(cur!=nullptr){ stk.push(cur); cur=cur->left; } TreeNode* temp = stk.top(); stk.pop(); if(prev!=nullptr && prev->val > temp->val){ if(first==nullptr) first = prev; second = temp; } prev= temp; if(temp->right!=nullptr) cur=temp->right; } int val = first->val; first->val = second->val; second->val = val; }
LeetCode-99-Recover Binary Search Tree
原文：https://www.cnblogs.com/nobodywang/p/10385482.html