📕문제

[Leetcode] 98. Validate Binary Search Tree

문제 설명

주어진 트리가 이진탐색트리(BST)인지 판별하는 문제다.

BST가 되기위한 조건

• 왼쪽 서브트리의 모든 값은 현재 노드 값보다 작아야 한다.
• 오른쪽 서브트리의 모든 값은 현재 노드 값보다 커야 한다.
• 모든 서브트리도 위 두 조건을 만족하는 BST여야 한다.

---

📝풀이

BST를 중위순회하면 오름차순이라는 점을 이용하였다.

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        stack = []
        curr = root
        prev = None
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            if prev and curr.val > prev.val:
                return False
            prev = curr
            curr = curr.right
        return True

• 탐색에 필요한 스택과 탐색 중 현재 노드를 저장할 변수 curr, 직전에 방문한 노드를 저장할 변수 prev를 설정한다.

1. 트리의 왼쪽 끝까지 내려가며 스택에 노드를 저장한다.
2. 스택에서 노드를 꺼내 curr값을 업데이트 한다.
3. 현재값이 이전값보다 크면 False를 반환한다.
4. prev값과 curr값을 업데이트한다.

• 위 과정을 반복한다. 탐색이 끝나면 문제가 없으므로 True를 반환한다.