持续创作,加速成长!这是我参与「日新计划 6 月更文挑战」的第14天,点击查看活动详情
前言
我们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Sw排序复杂度ift 算法题题解整理为文字版以方便大家学习与阅读。
Leet算法设计与分析Code 算法到目前我们已经更新到 98 期,我们会保持更新时算法的时间复杂度取决于间和进度(周一、周三、周五早上 9:00 发布),每期的内容不swift翻译多,我们希望大家可以在上班路上阅读,长久积累会有很大提升。
不积跬leetcode是干嘛的步,无以至千里;不积小流,无算法的特征以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的算法的空间复杂度是指需求。
难度水平:中等
1. 描述
给你二叉搜索树的根节点 root
,SwiftUI该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树 。
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 基础为核心的技术内容,也整理收集优秀的学习资料。