题目

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

摘自LeetCode99

解题方法

这道题在LeetCode中难度被定义为困难，主要是因为两方面：

• 第一如何找到错误交换的节点；
• 第二则是确定交换哪两个节点之后树可以恢复。

针对第一个问题可以使用中序遍历遍历二叉搜索树应该会得一个升序的数列，那么逆序的数字对就是错误的位置关系。例如示例一，中旬遍历的结果是3，2，1，很显然不符合升序要求。
那么是哪两个节点错误了呢？这里<3，2><2，1><3，1>都是错误的数字对，题目中已知只有两个节点错误地被交换，选择间距最大的一组数字对，即<3，1>，交换<3，1>两个节点即是正确结果。
另外，因为只需要记录逆序的数字对，实际上不用记录全部的中序遍历结果，只需要常数空间复杂度即可，记录间距最大的一组逆序数字对。

代码

在代码中进行详细注释

public void recoverTree(TreeNode root) {
    //初始化两个空间的数组用于记录错误交换的树节点
    TreeNode[] nodes = new TreeNode[]{null, null};
    //调用中序遍历方法找到错误交换的节点
    inorder(root, nodes);
    //交换两个节点
    if(nodes[1] != null){
        int tmp = nodes[0].val;
        nodes[0].val = nodes[1].val;
        nodes[1].val = tmp;
    }
}

private void inorder(TreeNode root, TreeNode[] nodes){
    if(null == root){
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    while(root != null){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        while(!stack.empty() && root  == null){
            root = stack.pop();
            //遍历到节点时，观察nodes[0]为null，则是第一个节点
            if(nodes[0] == null){
                nodes[0] = root;
            }else{
                //中序遍历逆序的一个数据对，因为只有两个节点错误，不一定是相邻的两个数字，可能是隔开的。
                //应该是间距最大的逆序数字对。
                if(nodes[0].val < root.val && null == nodes[1]){
                     //升序节点，nodes[1]为null则尚有节点没有遍历，nodes[0]记录逆序对的可能起始节点
                    nodes[0] = root;
                } else if(nodes[0].val < root.val && null != nodes[1]){
                     //如果升序节点，nodes[1]不为null，因为只有两个节点错误交换位置，则找到错误节点，停止程序
                    return;
                } else {
                    //找到逆序数字对，nodes[1]记录逆序对的结束节点
                    nodes[1] = root;
                }
            }
            root = root.right;
        }
    }
}