【1】【leetcode-99】 恢复二叉搜索树
（没思路）
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); } }