试题-有一颗二叉树的前序遍历和后续遍历分别是1,2,3,4和4,3,2,1，则该二叉树的中序遍历可能是(多选）

题目

有一颗二叉树的前序遍历和后续遍历分别是1,2,3,4和4,3,2,1，则该二叉树的中序遍历可能是(多选）

A.1,2,3,4

B.2,3,4,1

C.3,2,4,1

D.3,2,4,1

上一题 下一题

解答

正确答案是 ABD

其实有选项了就很简单,根据二叉树的定义,已知前序中序或者后序中序便可以得出唯一一棵二叉树,也就是说你只要把上述的前序遍历和中序遍历结合的树来和后序比较,一样则正确,不一样就是错的

C 3条回复评论

老瑭

好文，喜欢看，比书上的好

发表于 2024-07-03 22:00:00

0 0

雪糕乐

最笨的方法之一：分别用前序序列依次跟A、B、C、D四个选项的中序序列搭配，求其对应后序序列是否跟题目给的一致。即：前+中=>后

前序 + 中序 => 后序的关键点在于：（以A为例）

1、前序的第一个节点为根，即：1；

2、在中序中找到根节点的位置，划分左右子树（根节点左边的是左子树，根节点右边的是右子树），即2，3，4都是右子树；

3、现已确定根节点位置，再借助递归的思想分别求出其他节点位置。即：将根节点从原先序列中去掉，则前序序列｛2，3，4｝，中序序列｛2，3，4｝，再次利用步骤1、2做法，2为根节点，3，4是其右子树，这样确定下来2的位置；递归下去，确定所有树中节点位置。然后便可求得其后序序列｛4，3，2，1｝，与题目符合，A正确。

发表于 2018-11-01 15:51:27

0 0