0099：恢复二叉搜索树（★）

2015-04-09 约 424 字预计阅读 1 分钟次阅读

力扣第 99 题

题目

给你二叉搜索树的根节点 root ，该树中的恰好两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

树上节点的数目在范围 [2, 1000] 内
-2³¹ <= Node.val <= 2³¹ - 1

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

分析

二叉搜索树等价于其中序遍历的节点值是递增的
错误的节点处不递增
找出两处或一处不递增的地方，即可找到两个错误节点

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        a,b,p = None,None,TreeNode(-inf)
        sk = [(root,0)]
        while sk:
            u,flag = sk.pop()
            if flag:
                if u.val<p.val:
                    a,b = (a,u) if a else (p,u)
                p = u
            elif u:
                sk.extend([(u.right,0),(u,1),(u.left,0)])
        a.val,b.val = b.val,a.val

40 ms

*附加

要求 O(1) 空间，需要用 Morris 中序遍历。Morris 遍历减少了空间但也增加了时间，一般不用。

目录

0099：恢复二叉搜索树（★）

题目

分析

解答

*附加