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

D瓜哥

2020-06-21

算法

题目描述

一棵二叉树原本是二叉搜索树，但是其中有两个节点调换了位置，使得这棵二叉树不再是二叉搜索树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)

思路分析

一棵二叉搜索树，如果是中序遍历，那么，其序列正好是一个升序序列。如果序列中间出现了降序，那么就是树中错误的节点。这里有两种情况需要考虑：

如果两个节点正好相邻，那么降序的两个节点就是题目要求的节点。
如果两个节点不相邻，就会出现两次降序。很容易想到，“大”的元素跑前面，“小”的元素跑后面。在进行比较的时候，第一个降序时，前面大的元素是错误节点；第二次降序时，则是后面小的元素是错误节点。

有了上面的分析，就可以写代码了。

解题代码

中序遍历，可以用栈，也可以使用 Morris 遍历。前面正好学习了一下 Morris（详情请看：神奇的 Morris 树遍历），借此机会练练手：

/**
 * 基于 Morris 的中根遍历
 *
 * @author D瓜哥 · https://www.diguage.com
 */
public TreeNode[] getErrs(TreeNode head) {
    TreeNode[] result = new TreeNode[2];
    TreeNode curr = head;
    TreeNode mostRight = null;
    TreeNode prior = null;
    while (curr != null) {
        mostRight = curr.left;
        if (mostRight != null) {
            while (mostRight.right != null && mostRight.right != curr) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = curr;
                curr = curr.left;
                continue;
            } else {
                mostRight.right = null;
            }
        }
        if (prior != null) {
            if (prior.val > curr.val) {
                if (result[0] == null) {
                    result[0] = curr;
                    result[1] = prior;
                } else {
                    result[0] = curr;
                }
            }
        }
        prior = curr;
        curr = curr.right;
    }
    return result;
}