두 개의 순회 시퀀스 Preorder와 Postorder가 있다고 가정하고 이 두 시퀀스에서 이진 트리를 생성해야 합니다. 따라서 시퀀스가 [1,2,4,5,3,6,7], [4,5,2,6,7,3,1]이면 출력은
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ans :=pre[0] 값을 취하여 트리 노드를 만들고, stack :=빈 스택을 삽입하고, as
- i :=1 및 j :=0
- while i
- 스택 상단 값 =post[j]이면 j를 1만큼 증가시키고 스택에서 팝하고 다음 반복으로 이동
- node :=pre[i] 값으로 트리 노드 만들기
- 스택 상단 노드의 왼쪽 부분이 비어 있으면 스택 상단 노드의 왼쪽을 노드로 설정하고, 그렇지 않으면 스택 상단 노드의 오른쪽을 노드로 설정
- 스택에 노드 삽입
- i를 1 증가
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def height(root):
if root is None:
return 0
else :
# Compute the height of left and right subtree
l_height = height(root.left)
r_height = height(root.right)
#Find the greater one, and return it
if l_height > r_height :
return l_height+1
else:
return r_height+1
def print_given_level(root, level):
if root is None:
return
if level == 1:
print(root.data,end = ',')
elif level > 1 :
print_given_level(root.left , level-1)
print_given_level(root.right , level-1)
def level_order(root):
print('[', end = '')
h = height(root)
for i in range(1, h+1):
print_given_level(root, i)
print(']')
class Solution(object):
def constructFromPrePost(self, pre, post):
"""
:type pre: List[int]
:type post: List[int]
:rtype: TreeNode
"""
ans = TreeNode(pre[0])
stack = [ans]
i = 1
j = 0
while i < len(pre) and j < len(post):
if stack[-1].data == post[j]:
j+=1
stack.pop(-1)
continue
node = TreeNode(pre[i])
if not stack[-1].left:
stack[-1].left = node
else:
stack[-1].right = node
stack.append(node)
i+=1
return ans
ob = Solution()
pre = [1,2,4,5,3,6,7]
post = [4,5,2,6,7,3,1]
tree = ob.constructFromPrePost(pre, post)
level_order(tree) 입력
[1,2,4,5,3,6,7] [4,5,2,6,7,3,1] pre = [1,2,4,5,3,6,7] post = [4,5,2,6,7,3,1]
출력
[1,2,3,4,5,6,7,]