6.9

main.py

"""
# 문제 : 이진 트리 검증

주어진 이진 검색 트리가 이진 트리의 조건을 만족하는지 아닌지를 확인하라.

- 이진 트리는 부모 노드를 기준으로 왼쪽 노드는 부모 노드보다 작은 값이 보장되고
- 오른쪽 노드는 해당 노드보다 항상 큰 값이라는 보장이 된다.

### 아이디어 (재귀)

1. 트리의 최소값 / 최대값을 추적하기 위한 변수 설정
2. 트리를 방문한다.
 - 노드의 값이 low 보다 크고, high 보다 작은지를 확인한다.
 - 왼쪽 노드로 재귀 호출
 - 오른쪽 노드로 재귀 호출

### 아이디어 (반복 - 스택)

1. 트리의 최소값 / 최대값을 추적하기 위한 변수 설정
- low = float('-inf'), high = float('-inf')
2. 루트를 스택에 넣는다
3. 스택이 빌 때까지,
  - 노드의 값이 low 보다 크고, high 보다 작은지를 확인한다
  - 왼쪽 / 오른쪽 노드를 스택에 푸시한다.

### 아이디어 (중위 순회)

1. 트리를 중위 순회한다.
2. 다음 노드는 이전 노드보다 값이 항상 커야 한다.
  - 작다면 False (이진 검색 트리가 아님을 반환)
  - 크다면 계속 탐색
"""


class TreeNode:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val


def is_valid_bst(root: TreeNode) -> bool:
    if not root:
        return True

    if root.left and root.left.val > root.val:
        return False

    if root.right and root.right.val < root.val:
        return False

    return is_valid_bst(root.left) and \
           is_valid_bst(root.right)


def is_valid_bst1(root: TreeNode) -> bool:
    low = float('-inf')
    high = float('inf')

    def is_valid_bst_rec(node: TreeNode, low: int, high: int) -> bool:
        if not node:
            return True

        if node.data <= low or node.data >= high:
            return False

        return is_valid_bst_rec(node.left, low, node.val) \
               and is_valid_bst_rec(node.right, node.data, high)

    return is_valid_bst_rec(root, low, high)


def is_valid_bst2(root: TreeNode) -> bool:
    if not root:
        return True

    stack = []

    stack.append((root, float('-inf'), float('inf')))

    while stack:
        node, low, high = stack.pop()

        data = node.data
        if data <= low or data >= high:
            return False
        if node.left:
            stack.append((node.left, low, data))
        if node.right:
            stack.append((node.right, data, high))
    return True


def is_valid_bst3(root: TreeNode) -> bool:
    prev = float('-inf')

    def inorder_tree(node: TreeNode) -> bool:
        nonlocal prev
        if node == None:
            return True

        if not inorder_tree(node.left):
            return False

        if node.data <= prev:
            return False

        prev = node.data

        return inorder_tree(node.right)

    return inorder_tree(root)