BST 재건축
바이너리검색트리(BST)의 pre-order traversal은 트리의 루트 노드에서 시작하여 다음 순서로 각 노드를 방문하는 횡단 기법입니다.
- 현재 노드
- 왼쪽 하위 트리
- 오른쪽 하위 트리
BST의 pre-order traversal을 나타내는 정수배열이 주어지면, BST를 만든 후 루트 노드를 반환하는 함수를 작성하세요.
주어진 배열에는 pre-order traversal에 따른 순서대로 BST 노드의 값이 포함됩니다.
BST 노드에는 정수값, 왼쪽 및 오른쪽 자식 노드가 있습니다. BST 노드는 다음과 같은 BST 속성을 만족하는 경우에만 유효한 BST 노드라고 할 수 있습니다:
- BST 노드의 값은 왼쪽에 있는 모든 노드의 값보다 크다
- BST 노드의 값은 오른쪽에 있는 모든 노드의 값보다 적거나 동일하다
- BST 노드의 자식 노드는 유효한 BST 노드이거나 None / null이다.
예제 1
입력
preOrder = [10, 4, 2, 1, 5, 17, 19, 18]
