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

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

题目描述

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

思路分析

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

  1. 如果两个节点正好相邻,那么降序的两个节点就是题目要求的节点。

  2. 如果两个节点不相邻,就会出现两次降序。很容易想到,“大”的元素跑前面,“小”的元素跑后面。在进行比较的时候,第一个降序时,前面大的元素是错误节点;第二次降序时,则是后面小的元素是错误节点。

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

解题代码

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

/**
 * 基于 Morris 的中根遍历
 *
 * @author D瓜哥 · https://www.diguage.com
 */
public static 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;
}

得益于 Morris 的优秀本质,这个解法的时间复杂度是: O(n),空间复杂度是: O(1)。