★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（）➤GitHub地址：➤原文地址： ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★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,4,null,null,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,1,4,null,2], k = 1 3 / \ 1 4 \ 2输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], 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, k, &k2, &result)32 33 if k2 == 1 {34 k2 = 035 result = root.val36 }37 k2 -= 138 kthSmallest(root.right, k, &k2, &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, k, &count)18 }19 20 func traverseTree(_ root: TreeNode?, _ k: Int, _ count : inout Int) -> Int {21 var output = -1;22 if let left = root?.left {23 output = traverseTree(left, k, &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, k, &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 {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 ) -> 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 ()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, &result, k)25 if index == k {26 result = node!.val27 }28 index += 129 travesal(node!.right, &index, &result, k)30 }31 }32 }