二叉树遍历选择题技巧

一、根据先序和中序遍历求后序遍历

练习1

一棵二叉树的先序遍历为EFHIGJK,中序遍历为HFIEJKG,则后序遍历为 因为知道先序遍历的结果,可以得知E就是根结点,由此可得中序遍历结果中E左边为其左子树,右边为其右子树 之后就可以根据先序遍历的结果层层递推了 总结:做题技巧就是根据先序遍历的特性(根左右),在中序遍历的结果找到根结点,根据这一特性将中序遍历层层划分,最终能得到二叉树的形状也能求得后序遍历的结果 HIFJKGE。

练习2

先序序列为ABCDEF,中序序列为CBAEDF求后序序列

二、根据后序和中序遍历求先序遍历

练习1

已知一颗二叉树的后序序列为DABEC,中序序列为DEBAC,求先序序列 技巧根据后序序列最后一个为根结点,依次递推即可

练习2

后序:AEFDHZMG 中序: ADEFGHMZ 求先序


三、其他情况

1.根据先序和后序序列求中序 这种情况是不能唯一确定一颗二叉树的,结果有多种可能。 2.根据层序序列和中序序列求先序和后序 层序:ABCDEF 中序BADCFE

经验分享 程序员 微信小程序 职场和发展