Leetcode 255. Verify Preorder Sequence in Binary Search Tree

문제

Given an array of unique integers preorder, return true if it is the correct preorder traversal sequence of a binary search tree.

• 이진트리의 preorder 순회를 한 배열이 주어진다. 해당 트리가 BST인지 여부를 리턴하시오.

예시

Input: preorder = [5,2,1,3,6]
Output: true

제한

• $1 \le preorder.length \le 10^4$
• $1 \le preorder[i] \le 10^4$
• preorder의 모든 원소는 고유하다.

풀이

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        s = []
        lower = -float('inf')

        for n in preorder:
            if n < lower:
                return False

            while s and s[-1] < n:
                lower = s[-1]
                s.pop()

            s.append(n)

        return True

코드의 핵심 동작 원리를 부분별로 나눠보면 다음과 같습니다.

        s = []
        lower = -float('inf')

• s (Stack): 왼쪽 자식 방향으로 깊숙이 내려가는 경로(경과)를 임시로 기록하기 위해 스택을 사용합니다.
• lower (하한선): 현재 노드가 위치할 수 있는 최소 허용값(부모 노드의 값)을 의미합니다. Preorder(C → L → R)의 특성상, 누군가의 오른쪽 서브트리로 진입하는 순간 해당 서브트리 내부의 모든 노드 값은 그 부모 노드 값보다 반드시 커야 합니다. 초기 상태에서는 어떤 제약도 없으므로 하한선을 -inf로 설정합니다.

        for n in preorder:
            if n < lower:
                return False

• BST 검증: 새롭게 탐색하는 노드 n이 현재 유지되어야 할 하한선(lower)보다 작다면, 이는 이진 탐색 트리(BST)의 기본 조건(오른쪽 자식은 부모보다 커야 함)을 위배한 것입니다. 따라서 즉시 False를 리턴합니다.
• (첫 번째 값인 루트 노드는 하한선이 무한소(-inf)이므로 무사히 통과합니다.)

            while s and s[-1] < n:
                lower = s[-1]
                s.pop()

• 오른쪽 서브트리 전환 및 하한선 갱신: 스택의 맨 위 값(s[-1])보다 새로 들어온 값(n)이 더 크다는 것은, 더 이상 왼쪽으로 파고들지 않고 누군가의 오른쪽 서브트리로 넘어갔음을 의미합니다.
• 새로 들어온 값 n의 정확한 부모 노드 위치를 찾기 위해, n보다 작은 값들을 스택에서 계속 뽑아냅니다(pop).
• 스택에서 마지막으로 pop 된 값이 바로 새 노드 n의 직계 부모 노드가 됩니다. 이제부터 탐색할 노드들은 이 부모의 오른쪽 서브트리에 속하게 되므로, lower를 마지막으로 뽑아낸 부모 노드 값으로 갱신해 줍니다.

            s.append(n)

• 새 노드 n 역시 앞으로 탐색될 자신의 왼쪽 자식 노드들에 대해서는 부모 역할을 해야 하므로, 스택에 차례대로 쌓아줍니다.

        return True

• 배열의 끝까지 순회하는 동안 False가 한 번도 발생하지 않았다면, 주어진 배열의 모든 값이 BST의 규칙을 만족한다는 뜻이므로 최종적으로 True를 반환합니다.