Swift solution - Binary Search, DFS recursive, DFS iterative


  • 0
    class Solution {
        func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
            guard let root = root else {
                return 0
            }
            
            let count = countNodes(root.left)
        
            if k <= count {
                return kthSmallest(root.left, k)
            } else if k > count + 1 {
                return kthSmallest(root.right, k - 1 - count)
            }
            
            return root.val
        }
        
        func countNodes(_ root: TreeNode?) -> Int {
            guard let root = root else {
                return 0
            }
            
            return countNodes(root.left) + countNodes(root.right) + 1
        }
        
        func kthSmallest_DFS(_ root: TreeNode?, _ k: Int) -> Int {
            guard let root = root else {
                return 0
            }
            
            var count = k
            var result = 0
            
            helper(root, &count, &result)
            
            return result
        }
        
        func helper(_ root: TreeNode, _ count: inout Int, _ result: inout Int) {
            if let leftNode = root.left {
                helper(leftNode, &count, &result)
            }
            
            count -= 1
            if count == 0 {
                result = root.val
                return
            }
            
            if let rightNode = root.right {
                helper(rightNode, &count, &result)
            }
        }
        
        func kthSmallest_Stack(_ root: TreeNode?, _ k: Int) -> Int {
            var stack = [TreeNode]()
            var count = k
            var root = root
            
            while root != nil {
                stack.append(root!)
                root = root?.left
            }
            
            while count != 0 {
                let node = stack.removeLast()
                count -= 1
                if count == 0 {
                    return node.val
                }
                var rightNode = node.right
                while rightNode != nil {
                    stack.append(rightNode!)
                    rightNode = rightNode?.left
                }
            }
            
            return -1
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.