Table of Contents
定义树节点
一定要注意递归的思想
#定义node
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
由前序，中序到后序
前：GDAFEMHZ
中：ADEFGHMZ
preorder = 'GDAFEMHZ'
inorder = 'ADEFGHMZ'
preorder = [i for i in preorder]
inorder = [i for i in inorder]
# create_tree 和print_post 函数都不需要额外的记忆量
def create_tree(preorder, inorder):
if len(preorder) == 0:
return None
root = Node(preorder[0])
idx = inorder.index(preorder[0])
root.left = create_tree(preorder[1:idx+1], inorder[0:idx])
root.right = create_tree(preorder[idx+1:], inorder[idx+1:])
return root
def print_post(root):
if not root:
return []
res = []
res += print_post(root.left)
res += print_post(root.right)
res += [root.value]
return res
## 测试print_post函数
a, b, c, d, e, f, g = [Node(i) for i in range(1, 8)]
a.left = b
a.right = c
b.left = d
b.right = e
c.left = f
c.right = g
print_post(a)
[4, 5, 2, 6, 7, 3, 1]
# 测试
root = create_tree(preorder, inorder)
res = print_post(root)
print('Post order is : ', ''.join(res))
Post order is : AEFDHZMG
由后序，中序到前序
后：AEFDHZMG
中：ADEFGHMZ
postorder = 'AEFDHZMG'
inorder = 'ADEFGHMZ'
postorder = [i for i in postorder]
inorder = [i for i in inorder]
# create_tree 和print_post 函数都不需要额外的记忆量
def create_tree(postorder, inorder):
if len(postorder) == 0:
return None
root = Node(postorder[-1])
idx = inorder.index(postorder[-1])
root.left = create_tree(postorder[0:idx], inorder[0:idx])
root.right = create_tree(postorder[idx:-1], inorder[idx+1:])
return root
def print_pre(root):
if not root:
return []
res = [root.value]
res += print_pre(root.left)
res += print_pre(root.right)
return res
## 测试print_pre函数
a, b, c, d, e, f, g = [Node(i) for i in range(1, 8)]
a.left = b
a.right = c
b.left = d
b.right = e
c.left = f
c.right = g
print_pre(a)
[1, 2, 4, 5, 3, 6, 7]
# 测试
root = create_tree(postorder, inorder)
res = print_pre(root)
print('Pre order is : ', ''.join(res))
Pre order is : GDAFEMHZ
