이진 트리의 중위 및 후위 순회 시퀀스가 있다고 가정합니다. 이 시퀀스에서 트리를 생성해야 합니다. 따라서 후위 및 중위 시퀀스가 [9,15,7,20,3] 및 [9,3,15,20,7]이면 트리는 -
단계를 살펴보겠습니다 -
- 메서드가 preorder 및 inorder 목록과 함께 buildTree라고 가정합니다.
- root :=postorder의 마지막 노드, postorder의 첫 번째 노드 삭제
- root_index :=inorder 목록에서 root.val의 인덱스
- left 또는 root :=buildTree(root_index + 1에서 end, postorder까지의 inorder 부분집합)
- right 또는 root :=buildTree(인덱스 0에서 root_index, postorder까지의 inorder 부분집합)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def print_tree(root): #print using inorder traversal if root is not None: print_tree(root.left) print(root.data, end = ', ') print_tree(root.right) class Solution(object): def buildTree(self, preorder, inorder): if inorder: root = TreeNode(preorder.pop(0)) root_index = inorder.index(root.data) root.left = self.buildTree(preorder,inorder[:root_index]) root.right = self.buildTree(preorder,inorder[root_index+1:]) 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, 15, 7, 20, 3,