python 二叉树知前序、中序，打印后序

二叉树结构

class Node:
    def __init__(self, x):
        self.val=x
        self.left=None
        self.right=None

重建二叉树

def build(pre, mid):
    if len(pre)>0:
        root=Node(pre[0])
        idx=mid.index(root.val)
        root.left=build(pre[1:idx+1], mid[:idx])
        root.right=build(pre[idx+1:], mid[idx+1:])
        return root

后序打印

def postOrder(root):
    if root:
        postOrder(root.left)
        postOrder(root.right)
        print(root.val)

示例

pre=['A', 'B', 'D', 'E', 'G', 'C', 'F', 'H']
mid=['D', 'B', 'G', 'E', 'A', 'C', 'H', 'F']

root=build(pre, mid)
postOrder(root)

输出

['D', 'G', 'E', 'B', 'A', 'H', 'F', 'C']