已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列,并画出二叉树

中序序列：c，b，d，e，a，g，I，h，j，f
前序序列：a，b，c，d，e，f，g，h，I，j

zzp418591575 · 2018-4-30 01:53:11

我给楼主讲讲思想吧。
前序排序可以让你知道树的根节点是a，左孩子是b
将中序这样看聽cbde聽聽聽聽a聽聽聽聽glhjf
这样就分出了a的左右子树各所有的节点。
从cbde聽前序必然先读根，所以读b，可以这样看聽c聽聽b聽聽de
这样又分出来。如此反复，可以画出树。然后根据中序检查，某些只有一孩子的，到底是左孩子还是右孩子，因为左右孩子必然导致中序不一样。
后序：c聽e聽d聽b聽i聽j聽h聽g聽f聽a

wssznh1999 · 2018-4-30 01:53:12

后序序列：c,e,d,b,i,j,h,g,f,a
二叉树如图：

已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列,并画出二叉树

2 个回复