[Swift]LeetCode230. 二叉搜索树中第K小的元素 | Kth Smallest E

发布时间：2020-12-14 05:07:49 所属栏目：百科来源：网络整理

导读：Given a binary search tree,write a function? kthSmallest ?to find the?kth smallest element in it. Note:? You may assume k is always valid,1 ≤ k ≤ BST‘s total elements. Example 1: Input: root = [3,1,4,null,2],k = 1 3 / 1 4 ? 2Output: 1 E

Given a binary search tree,write a function?kthSmallest?to find the?kth smallest element in it.

Note:?
You may assume k is always valid,1 ≤ k ≤ BST‘s total elements.

Example 1:

Input: root = [3,1,4,null,2],k = 1
   3
  /  1   4
  ?  2
Output: 1

Example 2:

Input: root = [5,3,6,2,1],k = 3
       5
      /      3   6
    /    2   4
  /
 1
Output: 3

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

给定一个二叉搜索树，编写一个函数?kthSmallest?来查找其中第?k?个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,k = 1
   3
  /  1   4
  ?  2
输出: 1

示例 2:

输入: root = [5,k = 3
       5
      /      3   6
    /    2   4
  /
 1
输出: 3

进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化?kthSmallest?函数？

56ms

 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 kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {
16         func TreeSize(_ root: TreeNode?) -> Int {
17             if root == nil {
18                 return 0
19             }
20             return 1 + TreeSize(root?.left) + TreeSize(root?.right)
21         }
22         if root == nil {
23             return 0
24         }
25         var leftSize = TreeSize(root?.left)
26         if leftSize + 1 == k {
27             return root!.val
28         } else if leftSize >= k {
29             return kthSmallest(root?.left,k)
30         } else if leftSize + 1 < k {
31             return kthSmallest(root?.right,k - leftSize - 1)
32         }  
33         return 0
34     }
35 }

64ms

 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 kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {
16         var allNode = [Int]()
17         findAllNode(root,&allNode)
18         allNode.sort { (a,b) -> Bool in
19             a < b
20         }
21         return allNode[k - 1];
22     }
23     func findAllNode(_ node: TreeNode?,_ allNode: inout [Int]) -> Void {
24         if node == nil {
25             return
26         }
27         allNode.append(node!.val);
28         findAllNode(node!.left,&allNode)
29         findAllNode(node!.right,&allNode)
30     }
31 }

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     func kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {
16         var i = 1
17         var result = 0
18         inorderTraversal(root: root) { val in
19             if i == k {
20                 result = val
21             }
22             i += 1
23         }
24         return result
25     }
26     
27     private func inorderTraversal(root: TreeNode?,handler: (Int) -> Void) {
28         guard let root = root else { return }
29         inorderTraversal(root: root.left,handler: handler)
30         handler(root.val)
31         inorderTraversal(root: root.right,handler: handler)
32     }
33 }

72ms

 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 kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {
16         var k2 = k
17         var result = 0
18         kthSmallest(root,k,&k2,&result)
19         return result
20     }
21 
22     func kthSmallest(_ root: TreeNode?,_ k: Int,_ k2: inout Int,_ result: inout Int) {
23         guard let root = root else {
24             return
25         }
26 
27         if k2 == 0 {
28             return
29         }
30 
31         kthSmallest(root.left,&result)
32 
33         if k2 == 1 {
34             k2 = 0
35             result = root.val
36         }
37         k2 -= 1
38         kthSmallest(root.right,&result)
39     }
40 }

80ms

 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 kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {
16         var count = 0
17         return traverseTree(root,&count)
18     }
19     
20     func traverseTree(_ root: TreeNode?,_ count : inout Int) -> Int {
21         var output = -1;
22         if let left = root?.left {
23             output = traverseTree(left,&count)
24         }
25         
26         if output != -1 {
27             return output;
28         }
29         
30         count += 1        
31         if count == k {
32             return root!.val
33         }
34         
35         if let right = root?.right {
36             output = traverseTree(right,&count)
37         }
38         
39         return output
40     }
41 }

84ms

 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     
16     
17     var res = 0
18     var maxLength = 0
19     
20     func kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {
21         
22         maxLength = k
23         helper(node: root)
24         return res
25     }
26     
27     func helper(node: TreeNode?) {
28         guard let node = node else {
29             return
30         }
31         
32         helper(node: node.left)
33         maxLength -= 1
34         if maxLength == 0 {
35             res = node.val
36             return
37         }
38         helper(node: node.right)
39     }
40 }

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 kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {
16         var stack = [TreeNode]()
17         var valueArray = [Int]()
18         var root = root
19         
20         while !stack.isEmpty || root != nil {
21             while root != nil {
22                 stack.append(root!)
23                 root = root?.left
24             }
25             let curr = stack.removeLast()
26             valueArray.append(curr.val)
27             root = curr.right
28         }
29         
30         return valueArray[k - 1]
31     }
32 }

92ms

 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 kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {
16     guard let root = root else {
17         return -1
18     }
19     
20     var stack = [TreeNode]()
21     var curr: TreeNode? = root
22     var k = k
23     
24     while curr != nil || !stack.isEmpty {
25         if curr != nil {
26             stack.append(curr!)
27             curr = curr?.left
28         } else {
29             let node = stack.popLast()
30             k -= 1
31             
32             if k == 0 {
33                 return node!.val
34             }
35             
36             curr = node?.right
37         }
38     }
39       return -1
40     }
41 }

96ms

 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 kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {
16         let (_,result) = helper(root,k)
17         
18         return result ?? 0
19     }
20     
21     func helper(_ root: TreeNode?,_ k: Int) -> (Int,Int?) {
22         guard let root = root else { return (0,nil) }
23         
24         let (countL,vL) = helper(root.left,k)
25         if vL != nil {
26             return (countL,vL)
27         } else if countL == k - 1 {
28             return (k,root.val)
29         } else {
30             let (countR,vR) = helper(root.right,k - countL - 1)
31             if vR != nil {
32                 return (k,vR)
33             } else {
34                 return (countL + countR + 1,nil)
35             }
36         }
37         
38     }
39 }

96ms

 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     
16     class Queue<T> {
17   
18   private var array:[T]?
19   
20   func isEmpty() -> Bool {
21     
22     guard array != nil && array!.count != 0 else {
23       
24       return true
25     }
26     
27     return false
28   }
29   
30   func inQueue(_ val:T) {
31     
32     if array == nil {
33       
34       array = Array()
35     }
36     
37     array?.insert(val,at: 0)
38   }
39   
40   func outQueue() -> T? {
41     
42     return array?.popLast()
43   }
44 }
45 
46       func inorder(_ root:TreeNode?,_ queue:Queue<Int>) -> Void {
47     
48     if root == nil {
49       
50       return
51     }
52     
53     inorder(root?.left,queue)
54     
55     queue.inQueue(root!.val)
56     
57     inorder(root?.right,queue)
58   }
59 
60    func kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {
61    
62     guard root != nil else {
63       
64       return 0
65     }
66     
67     let queue = Queue<Int>()
68     
69     inorder(root,queue)
70     
71     var i = k
72     
73     while i > 1 {
74       
75       queue.outQueue()
76       
77       i -= 1
78     }
79     
80     return queue.outQueue()!
81   }
82 }

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     func kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {
16         guard let root = root else {
17             return 0
18         }
19         
20         var nodes: [TreeNode] = []
21         var node: TreeNode? = root
22         var index = 0
23         while !nodes.isEmpty || node != nil {
24             if node != nil {
25                 nodes.append(node!)
26                 node = node?.left
27             } else if let lastNode = nodes.popLast() {
28                 index += 1
29                 if index == k {
30                     return lastNode.val
31                 }
32                 node = lastNode.right
33             }
34         }
35         
36         return 0
37     }
38 }

140ms

 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 kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {
16         var count = 1
17         var result = 0
18         travesal(root,&count,&result,k)
19         return result
20     }
21     
22     func travesal(_ node: TreeNode?,_ index: inout Int,_ result: inout Int,_ k: Int) {
23         if node != nil && index <= k{
24             travesal(node!.left,&index,k)
25             if index == k {
26                 result = node!.val
27             }
28             index += 1
29             travesal(node!.right,k)
30         }
31     }
32 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!