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

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [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 }