수 많은 우문은 현답을 만든다

(Medium) BST 여부 검증 본문

코딩테스트/Tree

(Medium) BST 여부 검증

aiden.jo 2023. 10. 26. 01:38

Trees: Is This a Binary Search Tree?

 

문제링크

 

Input

Node List 가 들어온다.

 

Output

Yes (또는 No)

 

풀이:

더보기

def checkBST(root):
    // 검증할때는 함수를 하나 더 만들어야한다.
    def check(node, min_v, max_v):
        
        if node is None:
            return True //None이 아닌 True를 반환
        
        if min_v >= node.data or max_v <= node.data: //크고 작다보다 범위초과만 짚는다.
            return False
         
        return check(node.left, min_v, node.data) and (check(node.right, node.data, max_v))
        // 두 노드 검사 결과가 True여야 한다.
                
    return check(root, float('-inf'), float('inf'))
    //파이썬에서 무한대를 나타내는 방법으로 int로 표현하는 방법은 없다.

'코딩테스트 > Tree' 카테고리의 다른 글

(Medium) 허프만 코딩  (0) 2023.11.06
(Medium) BST LCA 구하기  (0) 2023.10.26
(Easy) 트리 높이 구하기  (0) 2023.10.24
(Easy) Maximum Depth of Binary Tree  (0) 2023.06.18
(Easy) Invert Binary Tree  (0) 2023.06.18