BinaryTree_LeetCode_230. Kth Smallest Element in a BST [swift]

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/?envType=study-plan-v2&envId=top-100-liked

 

문제 접근

BST이므로, 중위순회하면 오름차순 정렬이 된다.

array에 저장하여, count == k 일 때 마지막 element를 반환한다.

정답코드

/**
 * 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 ascending = [Int]()

    func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
        guard let root else { return 0 }
        if let lhs = root.left, ascending.count != k {
            traversal(lhs, k: k)
        }
        
        if ascending.count != k {
            ascending.append(root.val)
        }

        if let rhs = root.right, ascending.count != k {
            traversal(rhs, k: k)
        }

        return ascending.last!
    }
    
    func traversal(_ node: TreeNode, k: Int) {
        guard ascending.count != k else { return }
        if let lhs = node.left, ascending.count != k {
            traversal(lhs, k: k)
        }
        
        if ascending.count != k {
            ascending.append(node.val)
        }

        if let rhs = node.right, ascending.count != k {
            traversal(rhs, k: k)
        }

    }
}

 

다른 코드

고수의 코드는 도중에 멈추는 조건없이 모든 노드를 전부 순회하였다.

class Solution {
    func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
        var sortedArray = [Int]()
        traverse(root)
        func traverse(_ root: TreeNode?) {
            if root == nil { return }
            traverse(root?.left)
            sortedArray.append(root!.val)
             traverse(root?.right)
        }

        return sortedArray[k - 1]
    }
}