[Swift 알고리즘] LeetCode - 230. Kth Smallest Element in a BST

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

Kth Smallest Element in a BST - LeetCode

 

풀이

k번째 수를 BST에서 탐색하여 구하는 문제입니다.

처음엔 어떻게 해야하지 고민을 했는데요.

BST의 특성을 이용해 중위 탐색으로 해결하면 되겠다고 생각했습니다.

 

BST는 현재 노드를 기준으로 왼쪽은 무조건 작은 수가, 오른쪽은 무조건 큰 수가 존재합니다.

즉 중위 탐색을 하면 자연스럽게 sort가 되는 것이죠.

 

k번 value가 업데이트가 되면 재귀를 종료하고 답을 반환합니다.

 

전체 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    
    var count: Int = 0
    var value: Int = 0
    
    func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
        dfs(root, k)
        
        return value
    }
    
    func dfs(_ node: TreeNode?, _ k: Int) {
        guard let node = node else { return }
        
        dfs(node.left, k)
        
        if count < k {
            count += 1
            value = node.val
            dfs(node.right, k)
        }
    }
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.