1. 要点

二叉搜索树的特点：中序遍历结果递增，可用来做验证
复习下中序遍历（太久没写，写成前后序遍历的先push去了）

2. 题目

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

3. 示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

4. 示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

5. 提示：

树上节点的数目在范围 [2, 1000] 内
-231 <= Node.val <= 231 - 1

6. 代码

public void recoverTree(TreeNode root) {
        TreeNode firstWrongNode = null;
        TreeNode seccondWrongNode = null;
        TreeNode preNode = new TreeNode(Integer.MIN_VALUE);
        Stack<TreeNode> treeNodes = new Stack<>();
        TreeNode tmpRootNode =root;
        while (tmpRootNode!=null||!treeNodes.isEmpty()){
            if(tmpRootNode != null){
                treeNodes.push(tmpRootNode);
                tmpRootNode=tmpRootNode.left;
            }else{
                TreeNode currNode=treeNodes.pop();
                if (firstWrongNode == null && preNode.val> currNode.val){
                    firstWrongNode = preNode;
                }
                if (firstWrongNode != null && preNode.val > currNode.val){
                    seccondWrongNode = currNode;
                }
                preNode = currNode;
                tmpRootNode=currNode.right;
            }
        }
        int tmp =firstWrongNode.val;
        firstWrongNode.val=seccondWrongNode.val;
        seccondWrongNode.val=tmp;
    }