题解 | #找到搜索二叉树中两个错误的节点，空间O(1)#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 the root
     * @return int整型一维数组
     */
    //思想就是：二叉搜索树的中序遍历应该是单调递增序列，调换两个节点后，
    //原来递增的序列一定会产生两个 逆序对，每一对中必定有一个错误的数字。
    public int[] findError (TreeNode root) {
        int ans[] = new int[2] ;
        boolean findFirst = false ;//是否找到第一个错位的数字
        int last = -1 ;//记录中序遍历过程中上一次的 值
        Stack<TreeNode> st = new Stack<>() ;
        TreeNode t = root ;
        while(!st.isEmpty() || t != null) {
            while(t != null) {
                st.push(t) ;
                t = t.left ;
            }
            t = st.pop() ;
            //处理
            if(t.val < last) {//如果出现逆序，则挑出错误的 数字
                if(findFirst) {
                    ans[0] = t.val ;
                } else {
                    findFirst = true ;
                    ans[1] = last ;
                }
            }
            last = t.val ;
            t = t.right ;
        }
        return ans ; 
    }
}