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

概述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,

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

Example 2:

input: root = [5,3,6,2,1],k = 3       5      /      3   6    /    2   4  / 1Output: 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 = nil10  *         self.right = nil11  *     }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 019             }20             return 1 + TreeSize(root?.left) + TreeSize(root?.right)21         }22         if root == nil {23             return 024         }25         var leftSize = TreeSize(root?.left)26         if leftSize + 1 == k {27             return root!.val28         } 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 034     }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 = nil10  *         self.right = nil11  *     }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 in19             a < b20         }21         return allNode[k - 1];22     }23     func findAllNode(_ node: TreeNode?,_ allNode: inout [Int]) -> VoID {24         if node == nil {25             return26         }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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {16         var i = 117         var result = 018         inorderTraversal(root: root) { val in19             if i == k {20                 result = val21             }22             i += 123         }24         return result25     }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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {16         var k2 = k17         var result = 018         kthSmallest(root,k,&k2,&result)19         return result20     }21 22     func kthSmallest(_ root: TreeNode?,_ k: Int,_ k2: inout Int,_ result: inout Int) {23         guard let root = root else {24             return25         }26 27         if k2 == 0 {28             return29         }30 31         kthSmallest(root.left,&result)32 33         if k2 == 1 {34             k2 = 035             result = root.val36         }37         k2 -= 138         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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {16         var count = 017         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!.val33         }34         35         if let right = root?.right {36             output = traverseTree(right,&count)37         }38         39         return output40     }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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     16     17     var res = 018     var maxLength = 019     20     func kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {21         22         maxLength = k23         helper(node: root)24         return res25     }26     27     func helper(node: TreeNode?) {28         guard let node = node else {29             return30         }31         32         helper(node: node.left)33         maxLength -= 134         if maxLength == 0 {35             res = node.val36             return37         }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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {16         var stack = [TreeNode]()17         var valueArray = [Int]()18         var root = root19         20         while !stack.isEmpty || root != nil {21             while root != nil {22                 stack.append(root!)23                 root = root?.left24             }25             let curr = stack.removeLast()26             valueArray.append(curr.val)27             root = curr.right28         }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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {16     guard let root = root else {17         return -118     }19     20     var stack = [TreeNode]()21     var curr: TreeNode? = root22     var k = k23     24     while curr != nil || !stack.isEmpty {25         if curr != nil {26             stack.append(curr!)27             curr = curr?.left28         } else {29             let node = stack.popLast()30             k -= 131             32             if k == 0 {33                 return node!.val34             }35             36             curr = node?.right37         }38     }39       return -140     }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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {16         let (_,result) = helper(root,k)17         18         return result ?? 019     }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 = nil10  *         self.right = nil11  *     }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 true25     }26     27     return false28   }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       return51     }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 065     }66     67     let queue = Queue<Int>()68     69     inorder(root,queue)70     71     var i = k72     73     while i > 1 {74       75       queue.outQueue()76       77       i -= 178     }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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {16         guard let root = root else {17             return 018         }19         20         var nodes: [TreeNode] = []21         var node: TreeNode? = root22         var index = 023         while !nodes.isEmpty || node != nil {24             if node != nil {25                 nodes.append(node!)26                 node = node?.left27             } else if let lastNode = nodes.popLast() {28                 index += 129                 if index == k {30                     return lastNode.val31                 }32                 node = lastNode.right33             }34         }35         36         return 037     }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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func kthSmallest(_ root: TreeNode?,_ k: Int) -> Int {16         var count = 117         var result = 018         travesal(root,&count,&result,k)19         return result20     }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!.val27             }28             index += 129             travesal(node!.right,k)30         }31     }32 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode230. 二叉搜索树中第K小的元素 | Kth Smallest Element in a BST全部内容，希望文章能够帮你解决[Swift]LeetCode230. 二叉搜索树中第K小的元素 | Kth Smallest Element in a BST所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。