[leetcode] 98. Validate Binary Search Tree

Youn·2021년 9월 7일
0

Algorithm

목록 보기
27/37

문제 설명

링크
올바른 bst 인지 판단하는 문제 (left.val < root.val < right.val)

접근 1 - inorder Travel, 배열

  • left > root > right 순으로 탐색하면서 배열을 만듬
  • leftarr[-1] >= root.val 이면 false
  • rightarr[0] <= root.val 이면 false
  • 재귀로 구현

코드 1

    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        return self.isValidBSTHelper(root)

    def isValidBSTHelper(self, root) ->bool:
        left = right = []
        
        if root.left:
            left = self.isValidBSTHelper(root.left)
            if not left or (left and root.val <= left[-1]): return []
        if root.right:
            right = self.isValidBSTHelper(root.right)
            if not right or (right and root.val >= right[0]): return []
        return left + [root.val] + right

코드 2 - one time

  • 위와 접근은 동일하지만 중위순회로 중간에 확인없이 배열부터 다 만듬
  • sort 되어있는지 확인
    def isValidBST(self, root):
        output = []
        self.inOrder(root, output)
        
        for i in range(1, len(output)):
            if output[i-1] >= output[i]:
                return False

        return True

    def inOrder(self, root, output):
        if root is None:
            return
        
        self.inOrder(root.left, output)
        output.append(root.val)
        self.inOrder(root.right, output)
profile
youn

0개의 댓글