已知前序和中序遍历结果,输出后序遍历

思路如下:

  • 前序遍历的第一个元素是根元素;
  • 中序遍历根元素左边为左子树的中序遍历,右边为右子树的中序遍历;
    • 将前序遍历中所有左子树元素找出,得到左子树的前序遍历;
    • 将前序遍历中所有右子树元素找出,得到右子树的前序遍历;

在代码实现上,这里只要求输出,未要求内存中构建完整树结构

pre_list = [4, 9, 6, 3, 1, 2, 7, 8]
mid_list = [6, 9, 3, 1, 4, 8, 7, 2]

def post(pre, mid):
    if not pre:
        return
    index = mid.index(pre[0])
    post(pre[1:index + 1], mid[:index])
    post(pre[index + 1:], mid[index + 1:])
    print pre[0],

post(pre_list, mid_list)
Advertisements
此条目发表在未分类分类目录,贴了标签。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s