• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode99.恢复二叉搜索树|RecoverBinarySearchTree

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2:

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

  • A solution using O(n) space is pretty straight forward.
  • Could you devise a constant space solution?

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下,恢复这棵树。

示例 1:

输入: [1,3,null,null,2]

   1
  /
 3
  \
   2

输出: [3,1,null,null,2]

   3
  /
 1
  \
   2

示例 2:

输入: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

输出: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

进阶:

  • 使用 O(n) 空间复杂度的解法很容易实现。
  • 你能想出一个只使用常数空间的解决方案吗?

68ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     var biggerNode: TreeNode? = nil
16     var smallerNode: TreeNode? = nil
17     var node = TreeNode(-10000)
18     
19     func inorderTraverse(_ root: TreeNode) {
20         
21         if root.left != nil {
22             inorderTraverse(root.left!)
23         }
24         
25         if biggerNode == nil && root.val <= node.val {
26             biggerNode = node
27         }
28         if root.val <= node.val {
29             smallerNode = root
30         }
31         node = root
32         
33         if root.right != nil {
34             inorderTraverse(root.right!)
35         }
36         
37     }
38     func recoverTree(_ root: TreeNode?) {
39         guard let root = root else { return }
40         inorderTraverse(root)
41         let num = smallerNode!.val
42         smallerNode?.val = (biggerNode?.val)!
43         biggerNode?.val = num
44     }
45 }

88ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func recoverTree(_ root: TreeNode?) {
16         var firstElement: TreeNode? = nil
17         var secondElement: TreeNode? = nil
18         var prevElement = TreeNode(Int.min)
19 
20         traverse(root, &firstElement, &secondElement, &prevElement)
21 
22         let temp = firstElement?.val
23         firstElement?.val = secondElement?.val ?? 0
24         secondElement?.val = temp ?? 0
25     }
26 
27     fileprivate func traverse(_ root: TreeNode?, _ firstElement: inout TreeNode?, _ secondElement: inout TreeNode?, _ prevElement: inout TreeNode) {
28         guard let root = root else { return }
29 
30         traverse(root.left, &firstElement, &secondElement, &prevElement)
31 
32         if firstElement == nil && prevElement.val >= root.val {
33             firstElement = prevElement
34         }
35         if firstElement != nil && prevElement.val >= root.val {
36             secondElement = root
37         }
38         prevElement = root
39 
40         traverse(root.right, &firstElement, &secondElement, &prevElement)
41     }
42 }

100ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     var first: TreeNode?
16     var second: TreeNode?
17     var prev = TreeNode(Int.min)
18     
19     func recoverTree(_ root: TreeNode?) {
20         traverse(root)
21         
22         let temp = first!.val
23         first!.val = second!.val
24         second!.val = temp
25     }
26     
27     func traverse(_ root: TreeNode?) {
28         if root == nil {
29             return
30         }
31         
32         traverse(root?.left)
33         
34         if first == nil && prev.val >= root!.val {
35             first = prev
36         }
37         
38         if first != nil && prev.val >= root!.val {
39             second = root
40         }
41         prev = root!
42         
43         traverse(root?.right)
44     }
45 }

128ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func recoverTree(_ root: TreeNode?) {
16         guard root != nil else {
17             return
18         }
19         
20         var root = root
21 
22         var firstNode: TreeNode?
23         var secondNode: TreeNode?
24         var preNode: TreeNode?
25         
26         while root != nil {
27             if root!.left != nil {
28                 var pre = root!.left
29                 while pre!.right != nil && root! !== pre!.right! {
30                     pre = pre!.right
31                 }
32                 
33                 if pre!.right != nil && root === pre!.right! {
34                     if preNode != nil && preNode!.val >= root!.val {
35                         if firstNode == nil {
36                             firstNode = preNode
37                         }
38                         secondNode = root
39                     }
40                     preNode = root
41                     
42                     root = root!.right
43                     pre!.right = nil
44                 } else {
45                     pre!.right = root
46                     root = root!.left
47                 }
48                 
49             } else {
50                 
51                 if preNode != nil && preNode!.val >= root!.val {
52                     if firstNode == nil {
53                         firstNode = preNode
54                     }
55                     secondNode = root
56                 }
57                 preNode = root
58                 
59                 root = root!.right
60             }
61         }
62 
63         if firstNode != nil && secondNode != nil {
64             let temp = firstNode!.val
65             firstNode!.val = secondNode!.val
66             secondNode!.val = temp
67         }        
68     }
69 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift控制语句发布时间:2022-07-13
下一篇:
iOS开发 Swift开发数独游戏(一)发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap