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?
https://leetcode.com/problems/recover-binary-search-tree/
二叉排序树中有两个节点被交换了，要求把树恢复成二叉排序树。
最简单的办法，中序遍历二叉树生成序列，然后对序列中排序错误的进行调整。最后再进行一次赋值操作，但这个不符合空间复杂度要求。
需要用两个指针记录错误的那两个元素，然后进行交换。
怎样找出错误的元素？遍历二叉排序树，正确时应该是从小到大，如果出现之前遍历的节点比当前大，则说明出现错误。所以我们需要一个pre指针来指向之前经过的节点。
如果只有一处不符合从小到大，则只用交换这一个地方。第二个指针记录第二个异常点。
Github repository: https://github.com/huashiyiqike/myleetcode
//JAVA CODE：
public class Solution {
TreeNode first = null, second = null, pre = null;
//first larger than follow, second smaller than pre
public void helper(TreeNode root){
if(root.left != null) helper(root.left);
if(pre != null && root.val < pre.val){
if(first == null)
first = pre;
second = root;
}
pre = root;
if(root.right != null) helper(root.right);
}
public void recoverTree(TreeNode root) {
helper(root);
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
}
//C++ CODE：
#include <iostream>
#include <cstdlib>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; class Solution {
TreeNode *first = NULL, *second = NULL, *last = NULL;
public:
void inorder(TreeNode* root){
if(root->left != NULL){
inorder(root->left);
}
if(last != NULL && root->val < last->val){
if(first == NULL) first = last;
second = root;
}
last = root;
if(root->right != NULL) inorder(root->right);
}
void recoverTree(TreeNode* root) {
if(root == NULL) return;
inorder(root);
if(first && second)
std::swap(first->val, second->val);
}
};
#PYTHON CODE：
class Solution:
def inorderTravel(self, root, last):
if root.left:
last = self.inorderTravel(root.left, last)
if last and last.val > root.val:
if self.first is None:
self.first = last
self.second = root
last = root
if root.right:
last = self.inorderTravel(root.right, last)
return last def recoverTree(self, root):
if root is None:
return
self.first, self.second = None, None
self.inorderTravel(root, None)
self.first.val, self.second.val = self.second.val, self.first.val