（没思路）
99. 恢复二叉搜索树
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 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) 空间复杂度的解法很容易实现。
- 你能想出一个只使用常数空间的解决方案吗？
中序遍历，正常情况下为升序排列，结果中如果有一个降序对，说明该两个node需交换；若有两个降序对，说明第一对的前一个node和第二对的后一个node需要交换。
所谓简单的O(n)个空间的思路：
中序遍历得到数组，比如[1,3,2,4],在用一个hashmap<int,TreeNode>保存对象.
然后对数组排序，得到[1,2,3,4],对比得到2和3两个节点不一样，交换一下值即可。
下面实现进阶的常数空间思想：
在纸上写几个数组观察一下，可以发现，只需要找到三个结点（prev_first,first,second），就能进行交换，且只交换值是最方便的。
中序遍历，寻找第一个递减的节点，用prev记录前一个节点。
prev_first记录frist前驱，first记录现在。
再次寻找第二个递减的节点，second记录。若是找到了second，交换prev_first和second，若是没找到，交换prev_first和first
链接：https://www.nowcoder.com/questionTerminal/67c7172122b54b748e78eac7b183b5f3
来源：牛客网 public class Solution {
private TreeNode firstErrorNode=null;
private TreeNode secondErrorNode=null;
private TreeNode lastNode=null;
public void recoverTree(TreeNode root){
dealCore(root);
int temp=secondErrorNode.val;
secondErrorNode.val=firstErrorNode.val;
firstErrorNode.val=temp;
}
private void dealCore(TreeNode root){
if(root==null)return;
dealCore(root.left);
if(lastNode!=null){
if(lastNode.val>root.val){
if(firstErrorNode==null){
firstErrorNode=lastNode;
}
secondErrorNode=root;
}
}
lastNode=root;
dealCore(root.right);
}
}
看了思路：
public class RecoverTree {
TreeNode firstError = null;
TreeNode lastNode = null;
TreeNode secondError = null;
public void recoverTree(TreeNode root) {
inOrder(root);
int temp = firstError.val;
firstError.val = secondError.val;
secondError.val = temp;
}
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
if (lastNode != null) {
if (lastNode.val > root.val) {
if (firstError == null) {
firstError = lastNode;
}
secondError = root;
}
}
lastNode = root;
inOrder(root.right);
}
}