LeetCode 补充题 215. 二叉搜索树中被交换的两个节点值

约 4 分钟
文章信息 2 个分类 4 个标签
分类
补充题 中等
标签
深度优先搜索 树 二叉树 二叉搜索树

题目描述

:::fold-green 相关原题

LeetCode 原题： ✅ 99. 恢复二叉搜索树

LeetCode 原题要求交换错误节点的值以恢复树；本文只定位这两个值，按升序返回，不修改树。

:::

一棵严格二叉搜索树恰有两个节点值被交换，返回这两个值并按升序排列，不修改树。

示例 1：

输入： 交换后的中序序列 = [1,4,3,2,5]
输出： [2,4]

提示：

  • 至少两个节点。
  • 原树的节点值互不相同。
  • 恰好发生一次交换。

题意分析

值交换破坏了原本递增的中序序列，树的指针结构没有改变。无需修复树，只要在中序遍历中找出过早出现的大值和过晚出现的小值，再按升序返回。

解法：中序定位下降点

核心思路

[!blue]

严格 BST 的中序值原本递增。两个值互换后，较大的值被放到前面，较小的值被放到后面，因此观察相邻访问值的下降位置即可定位它们。

第一次出现 prev.val > cur.val 时，把前者记为 first；每次出现下降都更新 second 为后者。这样无论两个错误节点相邻还是相隔多项，都能保留前面的错误大值和后面的错误小值。

例如中序值 [1,4,3,2,5] 有 4>3 与 3>2 两次下降，first 固定为 4，second 最终更新为 2。本题返回 [2,4]，不执行原题最后交换节点值的动作。

解题步骤

  1. 用显式栈进行中序遍历，prev 保存上一次访问的节点。
  2. 遇到 prev.val>cur.val 时，若 first 尚未记录就令 first=prev。
  3. 每次下降都令 second=cur，再继续遍历并更新 prev。
  4. 返回 first、second 两个值的升序排列，不改动节点。

代码实现

class Solution {
    public int[] swappedValues(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        TreeNode prev = null;
        TreeNode first = null;
        TreeNode second = null;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();

            if (prev != null && prev.val > cur.val) {
                if (first == null) {
                    first = prev;
                }

                second = cur;
            }

            prev = cur;
            cur = cur.right;
        }

        return new int[] {
            Math.min(first.val, second.val),
            Math.max(first.val, second.val)
        };
    }
}

func swappedValues(root *TreeNode) []int {
    stack := make([]*TreeNode, 0)
    cur := root
    var prev, first, second *TreeNode

    for cur != nil || len(stack) > 0 {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }

        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if prev != nil && prev.Val > cur.Val {
            if first == nil {
                first = prev
            }
            second = cur
        }
        prev = cur
        cur = cur.Right
    }

    return []int{
        min(first.Val, second.Val),
        max(first.Val, second.Val),
    }
}

复杂度分析

  • 时间复杂度：$O(n)$。
  • 空间复杂度：额外空间 $O(h)$。

关键点总结

[!green]

中序序列的下降位置揭示错误值：第一次下降取前者，最后一次下降取后者；返回二者的有序值。

易错点总结

[!yellow]

  • 相邻交换只出现一次下降，非相邻交换会出现两次；不能找到第一次下降就结束。
  • first 只在第一次下降时设置，second 则需要在最后一次下降时更新。
  • 本题保证恰有一次交换，因此最终两个错误节点都能找到；只返回值，不执行恢复操作。

相似题目

题目 难度 关联与区别
99. 恢复二叉搜索树 中等 都根据中序序列的下降位置定位被交换的两个值；该题需要交换值恢复树，本题仅按升序返回两个值，不修改树。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/162534057026
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！