二叉树遍历选择题技巧
一、根据先序和中序遍历求后序遍历
练习1
一棵二叉树的先序遍历为EFHIGJK,中序遍历为HFIEJKG,则后序遍历为 因为知道先序遍历的结果,可以得知E就是根结点,由此可得中序遍历结果中E左边为其左子树,右边为其右子树 之后就可以根据先序遍历的结果层层递推了 总结:做题技巧就是根据先序遍历的特性(根左右),在中序遍历的结果找到根结点,根据这一特性将中序遍历层层划分,最终能得到二叉树的形状也能求得后序遍历的结果 HIFJKGE。
练习2
先序序列为ABCDEF,中序序列为CBAEDF求后序序列
二、根据后序和中序遍历求先序遍历
练习1
已知一颗二叉树的后序序列为DABEC,中序序列为DEBAC,求先序序列 技巧根据后序序列最后一个为根结点,依次递推即可
练习2
后序:AEFDHZMG 中序: ADEFGHMZ 求先序
三、其他情况
1.根据先序和后序序列求中序 这种情况是不能唯一确定一颗二叉树的,结果有多种可能。 2.根据层序序列和中序序列求先序和后序 层序:ABCDEF 中序BADCFE