Python의 Postorder 및 Inorder에서 이진 트리 구성

이진 트리의 중위 및 후위 순회 시퀀스가 ​​있다고 가정합니다. 이 시퀀스에서 트리를 생성해야 합니다. 따라서 후위 및 중위 시퀀스가 ​​[9,15,7,20,3] 및 [9,3,15,20,7]이면 트리는 -

단계를 살펴보겠습니다 -

• build_tree() 메서드를 정의하면 순서가 뒤바뀔 것입니다. -

• 중위 목록이 비어 있지 않은 경우 -

  • root :=postorder의 마지막 값으로 트리 노드를 만든 다음 해당 요소를 삭제합니다.

  • ind :=inorder 목록의 루트 데이터 인덱스

  • root의 오른쪽 :=build_tree(index ind에서 end까지 inorder, postorder)

  • 루트 왼쪽 :=build_tree(0에서 인덱스 ind - 1까지 순서대로, 후위)

• 루트 반환

예시

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

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
class Solution(object):
   def buildTree(self, inorder, postorder):
      if inorder:
         root = TreeNode(postorder.pop())
         ind = inorder.index(root.data)
         root.right = self.buildTree(inorder[ind+1:],postorder)
         root.left = self.buildTree(inorder[:ind],postorder)
         return root
ob1 = Solution()
print_tree(ob1.buildTree([9,3,15,20,7], [9,15,7,20,3]))

입력

[9,3,15,20,7]
[9,15,7,20,3]

출력

[9,3,15,20,7]