题解 | #找到搜索二叉树中两个错误的节点#

import java.util.*;

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

public class Solution {
    /**
    * 上一次中序遍历过的节点
    */
    private TreeNode prev;
    /**
     * 第一个错误节点
     */
    private TreeNode first;
    /**
     * 第二个错误节点
     */
    private TreeNode second;

    // 查找树节点逆序对--中间过程操作
    private void find(TreeNode node) {
        // 出现了逆序对,出现逆序对可能性有两种：
        // 第一种两个节点中序遍历中节点挨着，另外一种不挨着，无论哪种，第一个遇到的逆序对第一个节点就是错误值，遇到第二个逆序对的第二个值就是错误值
        if (prev != null && prev.val > node.val) {
            // 第2个错误节点：最后一个逆序对中较小的那个节点
            second = node;

            // 第1个错误节点：第一个逆序对中较大的那个节点
            if (first != null) return;
            first = prev;
        }
        prev = node;
    }
    /**
     *
     * @param root TreeNode类 the root
     * @return int整型一维数组
     */
    public int[] findError (TreeNode root) {
        // write code here
        findWrongNodes(root);
        // 交换2个错误节点的值
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
        return new int[]{first.val,second.val};
    }
    private void findWrongNodes(TreeNode root) {
        if (root == null) return;
        findWrongNodes(root.left);
        find(root);
        findWrongNodes(root.right);
    }

}

解题思想：

* 方式一：递归中序遍历查找逆序对

* 方式二：morris遍历：线索二叉搜索树找逆序对