BST_Leetcode_98. Validate Binary Search Tree [swift]

https://leetcode.com/problems/validate-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked

 

문제접근

1. 모든 노드에 대해 중위순회하며 val을 array.append
2. 중복 값을 제거하고, sort하여 기존 값과 비교

이렇게 해서 성능상 문제가 발생하면 다른 구현방법을 사용하려했었다.

근데 문제가 널럴하였음

아래는 다른 구현방법 문제 접근

1. (반복문을 통해) 모든 노드에 대해 중위순회 시작. var current: Int에 node.val을 저장할 것
2. current와 node.val을 비교, node.val > current이 아니라면, break. else current = node.val

정답코드

/**
 * 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 bin = [Int]()
    func isValidBST(_ root: TreeNode?) -> Bool {
        guard let root else { return false }
        if let lhs = root.left {
            traversal(to: lhs)
        }
        bin.append(root.val)
        if let rhs = root.right {
            traversal(to: rhs)
        }
        return bin == Array(Set(bin)).sorted()
    }

    func traversal(to root: TreeNode) {
        if let lhs = root.left {
            traversal(to: lhs)
        }
        bin.append(root.val)
        if let rhs = root.right {
            traversal(to: rhs)
        }
    }
}