이진 트리의 inorder 및 preorder 순회 시퀀스가 있다고 가정합니다. 이 시퀀스에서 트리를 생성해야 합니다. 따라서 preorder 및 inorder 시퀀스가 [3,9,20,15,7] 및 [9,3,15,20,7]이면 트리는 -
가 됩니다.
단계를 살펴보겠습니다 -
- 메서드가 preorder 및 inorder 목록과 함께 buildTree라고 가정합니다.
- root :=선주문에서 첫 번째 노드, 선주문에서 첫 번째 노드 삭제
- root_index :=inorder 목록에서 root.val의 인덱스
- left 또는 root :=buildTree(선주문, 0에서 root_index까지의 중위 하위 집합)
- 오른쪽 또는 루트 :=buildTree(선주문, root_index + 1에서 끝까지 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([3,9,20,15,7], [9,3,15,20,7]))
입력
[3,9,20,15,7] [9,3,15,20,7]
출력
9, 3, 15, 20, 7,