首页 > 试题广场 >

有一颗二叉树的前序遍历和后续遍历分别是1,2,3,4和4,3

[不定项选择题]
有一颗二叉树的前序遍历和后续遍历分别是1,2,3,4和4,3,2,1，则该二叉树的中序遍历可能是 
  • 1,2,3,4
  • 2,3,4,1
  • 3,2,4,1
  • 4,3,2,1
查看正确选项
添加回答
_遇见时光头像 _遇见时光
A也是可能的吧
发表于 2016-03-23 20:42:42 回复(4)
焦佐伊头像 焦佐伊
这道题只要是没有分支的树都符合，4个节点3条边，每条边可能有两个朝向，总共2^3=8种情况。
发表于 2016-08-02 13:31:43 回复(0)
日照香炉头像 日照香炉
看来牛客的答案也是自己做的，并不准确。。。
发表于 2016-03-25 14:34:53 回复(0)
下里巴人头像 下里巴人
总共有8种可能情况：4321    3421    2431    2341    1234    1243    1432    1342

编辑于 2016-03-28 00:17:40 回复(0)
Nothing&All头像 Nothing&All
中序遍历可能有四种：①4,3,2,1 ②3,4,2,1 ③2,4,3,1 ④ 2,3,4,1
如图：

还有一个是A选项。1-2-3-4这种的。
好像还有1432,1342,1243。一共8种
编辑于 2016-03-24 16:20:35 回复(5)
47头像 47
其实有选项了就很简单,根据二叉树的定义,已知前序中序或者后序中序便可以得出唯一一棵二叉树,也就是说你只要把上述的前序遍历和中序遍历结合的树来和后序比较,一样则正确,不一样就是错的
发表于 2016-08-01 16:44:33 回复(1)
MSean头像 MSean
最笨的方法之一：分别用前序序列依次跟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正确。

发表于 2016-08-02 17:21:43 回复(0)
hflee头像 hflee
全部8种[吐血]如有遗漏或错误请指出
编辑于 2017-03-22 20:46:39 回复(3)
__sgf__头像 __sgf__
穷举法，用四个答案的中序遍历和题目的前序遍历1234画出一棵树（前序+中序能确定唯一的树），然后看这棵树的后序遍历是不是4321。
发表于 2022-03-01 10:06:17 回复(1)
海带ど仙女ど头像 海带ど仙女ど
除了题目给出的以外，还有四种可能
发表于 2018-04-01 16:56:31 回复(0)
爱吃青菜皮卷面的byr头像 爱吃青菜皮卷面的byr
做对这道题的关键是能理解好前序遍历，中序遍历，后续遍历的 概念：

发表于 2017-02-16 13:40:12 回复(0)
宝宝^_^头像 宝宝^_^
解答：其实从前序遍历和后续遍历是相反的可以得出结论，这个二叉树每个节点只能有一个叶子，如果存在两个叶子的节点，那么肯定顺序不是相反的。所以，这个二叉树只要是一条线就行。挨个构造可以得出，ABC都可以。
发表于 2016-07-23 10:12:58 回复(1)
纯真的小龙虾愿offer多多头像 纯真的小龙虾愿offer多多
这段话是引用前面大牛焦佐伊的：这道题只要是没有分支的树都符合，4个节点3条边，每条边可能有两个朝向，总共2^3=8种情况。
下图是我受其启发画的

编辑于 2023-12-04 16:39:55 回复(0)
牛客512762612号头像 牛客512762612号
前序和后序相反，没有度尾2的节点
发表于 2022-02-26 20:05:09 回复(0)
哈萨克塔吉隆头像 哈萨克塔吉隆
1                                      1            1           1                              1              1                        1                       1
    \                                 /              /                \                         /                    \                    /                              \
       2                          2             2                    2                 2                          2             2                                  2
         \                       /                    \               /                 /                               \                 \                              /
           3                 3                        3          3                3                                  3                 3                       3
             \              /                         /                \                  \                             /                         \                 /
               4       4                      4                       4                  4                   4                                4          4
1-2-3-4              4-3-2-1          2-4-3-1        1-3-4-2            3-4-2-1             4-3-2-1          2-3-4-1          1-4-3-2

发表于 2018-04-07 15:18:36 回复(0)
ray_am头像 ray_am
其实我是按照答案中，中序遍历和前序遍历确定后序的，看看后序遍历是不是1234
发表于 2017-08-24 08:46:00 回复(0)
sunlight_run头像 sunlight_run
这道题利用结论：前序后序相反，就说明树的任意节点度为1 ，这样就很容易画出来了
发表于 2017-06-29 16:50:59 回复(0)
Ｍe怤畢炜eＭ头像 Ｍe怤畢炜eＭ
前序遍历和后序遍历的顺序正好相反，表明树的每一层都只有一个节点。
NLR = LRN（逆序）树除了叶子节点外 每个节点的左子树或者是右子树为空。按照这个规律就可以画出各种对应树的形状。只有C选项不满足条件 所以选择ABD
发表于 2016-08-01 10:55:33 回复(0)
程序的智慧头像 程序的智慧
上面的圈内是根据前序列出的所有可能的情况
下面的圈内打对勾的是符合条件的
总共有八种
发表于 2016-07-26 11:18:16 回复(0)
啥头像 啥
可采用排除法来做
发表于 2016-04-15 11:05:06 回复(0)
提交观点

问题信息

树
来自：2016乐视暑期实习生...
难度：
25条回答 22817浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号