이진 검색 트리의 후위 순회 시퀀스가 있다고 가정합니다. 이 시퀀스에서 트리를 생성해야 합니다. 따라서 후위 순서가 [9,15,7,20,3]이면 트리는 -
가 됩니다. 
트리를 형성하려면 중위 순회도 필요하지만 이진 탐색 트리의 경우 중위 순회는 정렬된 형식이 됩니다.
단계를 살펴보겠습니다 -
-
Inorder =postorder 순회 정렬된 목록입니다.
-
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() postorder = [3,9,20,15,7] inorder = list(sorted([3,9,20,15,7])) print_tree(ob1.buildTree(inorder, postorder))
입력
[9,3,15,20,7] [9,15,7,20,3]
출력
[3,7,9,15,20]