Python의 Preorder Traversal에서 이진 검색 트리 구성

주어진 선주문 순회와 일치하는 이진 검색 트리를 생성해야 한다고 가정합니다. 따라서 선주문 순회가 [8,5,1,7,10,12]와 같으면 출력은 [8,5,10,1,7,null,12]가 되므로 트리는 -

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 루트 :=0 ^번째 선주문 순회 목록의 노드
• stack :=스택, 스택에 루트 푸시
• 선주문 목록의 두 번째 요소에서 각 요소 i에 대해
  • i :=값이 i인 노드
  • 만약 i의 값이 <스택 상단 요소의 상단이면
    • 스택 상단 노드의 왼쪽 :=i
    • 스택에 i 삽입
  • 그렇지 않으면
    • 스택이 비어 있지 않고 스택 최상위 요소 값 의 값인 동안
    • last :=스택의 맨 위
    • 스택에서 요소 팝
  • 마지막 노드의 오른쪽 :=i
  • 스택에 i 삽입

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution(object):
   def bstFromPreorder(self, preorder):
      """
      :type preorder: List[int]
      :rtype: TreeNode
      """
      root = TreeNode(preorder[0])
      stack = [root]
      for i in preorder[1:]:
         i = TreeNode(i)
         if i.val<stack[-1].val:
            stack[-1].left = i
            stack.append(i)
         else:
            while stack and stack[-1].val<i.val:
               last = stack.pop(-1)
            last.right = i
            stack.append(i)
      return root

입력

[8,5,1,7,10,12]

출력

[8,5,10,1,7,null,12]