LeetCode - #99 恢复二叉搜索树

前言

我们社区陆续会将顾毅（Netflix 增长黑客，《iOS 面试之道》作者，ACE 职业健身教练。）的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新到 98 期，我们会保持更新时间和进度（周一、周三、周五早上 9:00 发布），每期的内容不多，我们希望大家可以在上班路上阅读，长久积累会有很大提升。

不积跬步，无以至千里；不积小流，无以成江海，Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：中等

1. 描述

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

2. 示例

示例 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^31 <= Node.val <= 2^31 - 1

3. 答案

/**
 * Primary idea: Morris Traversal (In-order)
 * The key is to construct the connection between child & parent
 * 1) If cur.left == nil:
 *      - Output cur.val
 *      - Set cur = cur.right
 * 2) If cur.left != nil:
 *      - Find the precursor of cur, precursor
 *      i. If precursor.right == nil:
 *          - Set precursor.right = cur
 *          - Set cur = cur.left
 *      ii. If precursor.right != nil (which means precursor.right === cur):
 *          - Set precursor.right = nil (Recover the structure of original tree)
 *          - Output cur.val
 *          - Set cur = cur.right
 * 3) Repeat 1) & 2) until cur == nil
 *
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */

class RecoverBinarySearchTree {
    func recoverTree(_ root: TreeNode?) {
        var pre: TreeNode?  // Store the pre-node in the sorted list
        var first: TreeNode?
        var second: TreeNode?
        
        // Morris Traversal
        var cur = root
        var precursor: TreeNode?
        while cur != nil {
            // 2) If cur.left != nil:
            if cur!.left != nil {
                // Find the precursor of cur
                precursor = cur!.left
                while precursor!.right != nil && precursor!.right !== cur {
                    precursor = precursor!.right
                }
                // 2)ii. If the connection already existed
                if precursor!.right === cur {
                    // First time we meet pre.val >= cur.val must be the first node
                    // But the second node need to be the last time we meet pre.val >= cur.val
                    // e.g 1, 4, 3, 5, 6 v.s 1, 5, 4, 3, 6
                    if pre != nil && pre!.val >= cur!.val {
                        if first == nil {
                            first = pre
                            second = cur
                        } else {
                            second = cur
                        }
                    }
                    pre = cur!
                    precursor!.right = nil
                    cur = cur!.right
                // 2)i. Construct the connection
                } else {
                    precursor!.right = cur
                    cur = cur!.left
                }
            // 1) If cur.left == nil:
            } else {
                if pre != nil && pre!.val >= cur!.val {
                    if first == nil {
                        first = pre
                        second = cur
                    } else {
                        second = cur
                    }
                }
                pre = cur!
                cur = cur!.right
            }
        }
        
        // Swap the 2 nodes
        if first != nil && second != nil {
            swap(&first!.val, &second!.val)
        }
    }
}

• 主要思想：关键是要建立孩子和父母之间的联系。
• 时间复杂度： O(n)
• 空间复杂度： O(1)

该算法题解的仓库：LeetCode-Swift

点击前往 LeetCode 练习

关于我们

我们是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。

后续还会翻译大量资料到我们公众号，有感兴趣的朋友，可以加入我们。