Leetcode: Validate Binary Search Tree, 이진 탐색 트리 검증

문제설명

• 인자로 주어진 노드가 이진 탐색 트리인지 판별하라.
• 이진 탐색 트리는 왼쪽 서브 트리는 노드의 값(key)보다 작아야 한다. 오른쪽 서브 트리는 노드의 값(key)보다 커야 한다.

문제풀이

• TreeNode와 최소값, 최대값을 하나의 타입에 캡슐화하기 위하여 BinarySearchTree를 임의로 정의하였다.
• 왼쪽 자식 노드를 탐색할 때는 부모인 현재 노드의 값이 최대값이 된다.
• 오른쪽 자식 노드를 탐색할 때는 부모인 현재 노드의 값이 최소값이 된다.

// MARK: - Definition
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
      }
}
extension TreeNode {
    static func from(_ arr: [Int?]) -> TreeNode? {
        guard let firstElement = arr[0] else {
            return nil
        }
        let root = TreeNode(firstElement)
        var queue = [TreeNode]()
        queue.append(root)

        var index = 1
        while !queue.isEmpty && index < arr.count {

            let node = queue.removeFirst()
            if let leftVal = arr[index] {
                let left = TreeNode(leftVal)
                node.left = left
                queue.append(left)
            }
            if index+1 < arr.count, let rightVal = arr[index+1]{
                let right = TreeNode(rightVal)
                node.right = right
                queue.append(right)
            }
            index += 2
        }

        return root
    }

}

// MARK: - Answer
func isValidBST(_ root: TreeNode?) -> Bool {
    guard let root = root else {
        return false
    }

    var queue = [BinarySearchTreeNode]()
    queue.append(BinarySearchTreeNode(node: root, min: Int.min, max: Int.max))

    while !queue.isEmpty {
        let binNode = queue.removeFirst()
        let currentNode = binNode.node
        //print("node : \(binNode.node.val), left : \(currentNode.left?.val), right : \(currentNode.right?.val), min: \(binNode.min), max: \(binNode.max)")
        if binNode.min >= currentNode.val || binNode.max <= currentNode.val {
            return false
        }

        if let leftNode = currentNode.left {
            queue.append(BinarySearchTreeNode(node: leftNode, min: binNode.min, max: currentNode.val))
        }
        if let rightNode = currentNode.right {
            queue.append(BinarySearchTreeNode(node: rightNode, min: currentNode.val, max: binNode.max))
        }

    }
    return true
}
public struct BinarySearchTreeNode {
    let node: TreeNode
    let min: Int
    let max: Int
}

// MARK: - Test
var node1: TreeNode?
node1 = TreeNode.from([5,4,6,nil,nil,3,7])
print(isValidBST(node1)) // false

node1 = TreeNode.from([2,1,3])
print(isValidBST(node1)) // true

node1 = TreeNode.from([5,1,4,nil,nil,3,6])
print(isValidBST(node1)) // false

node1 = TreeNode.from([1])
print(isValidBST(node1)) // true