Python에서 스택을 사용하여 주어진 후위 순회에서 BST 구성

이진 검색 트리에 대한 하나의 후위 순회가 있다고 가정합니다. 여기서 바이너리 검색 트리를 찾아야 합니다.

따라서 입력이 [6, 12, 10, 55, 45, 15]와 같으면 출력은

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

• solve() 함수를 정의합니다. 우편 주문이 필요합니다

• n :=포스트오더의 크기

• root :=postorder의 마지막 요소로 새 트리 노드 만들기

• stk :=스택

• stk에 루트 삽입

• 나는 :=n - 2

• i>=0인 동안 수행

  • x :=값이 postorder[i]인 새 노드 만들기

  • stk가 비어 있지 않은 동안 postorder[i]

    • temp :=stk의 상단

    • stk에서 최상위 요소 삭제

  • temp가 null이 아니면

    • temp.left :=x

  • 그렇지 않으면

    • stk 상단 요소의 오른쪽 :=x

  • x를 stk에 삽입

  • 나는 :=나는 - 1

• 루트 반환

• 주요 방법에서 다음을 수행하십시오 -

• 반환 해결(포스터)

예시

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

class TreeNode:
   def __init__(self, data = 0):
      self.val = data
      self.left = None
      self.right = None
def solve(postorder):
   n = len(postorder)
   root = TreeNode(postorder[n - 1])
   stk = []
   stk.append(root)
   i = n - 2
   while ( i >= 0):
      x = TreeNode(postorder[i])
      temp = None
      while (len(stk) > 0 and postorder[i] < stk[-1].val) :
         temp = stk[-1]
         stk.pop()
      if (temp != None):
         temp.left = x
      else:
         stk[-1].right = x
      stk.append(x)
      i = i - 1
   return root
def build_tree(postorder):
   return solve(postorder)
def inord( node):
   if node:
      inord(node.left)
      print( node.val, end = " ")
      inord(node.right)
postorder = [6, 12, 10, 55, 45, 15]
root = build_tree(postorder)
print( "Inorder traversal:", end = " ")
inord(root)

입력

[6, 12, 10, 55, 45, 15]

출력

6 10 12 15 45 55