首页 > 试题广场 >

若一棵具有n(n0)个结点的二叉树的先序序列与后序序列正好

[单选题]
若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定？ 
  • 结点均无左孩子的二叉树
  • 结点均无右孩子的二叉树
  • 高度为n的二叉树
  • 存在度为2的结点的二叉树
查看正确选项
添加回答
陋室头像 陋室
原理如下：
先序遍历顺序是：M-L-R;
后序遍历顺序是：L-R-M;
可以看到，只有中间的结点（M）顺序变化了，左右结点相对位置是不变的。那可以推断出，要满足题意的话“二叉树的先序序列与后序序列正好相反”，说明整个二叉树左子树或者右子树有一个没有（遍历就成了，先：M-L ；后：L-M 或者  先：M-R ；后：R-M ）也就是必然是一条链。
编辑于 2015-08-29 11:30:04 回复(0)
讨鬼头像 讨鬼
发表于 2015-08-27 08:35:42 回复(5)
Geniuspyh头像 Geniuspyh
首先AB选项都是符合题意的，但不一定就是A或B，先序序列和后序序列正好相反，则说明他一定是单支树，已知一共有n个节点，且所以C选项说其高度为n，则C描述的就是单支树，故选C
发表于 2020-03-08 22:47:05 回复(0)
小娇娇头像 小娇娇
没有左子树或者没有右子树，Mark一下，考虑不周
发表于 2016-08-30 12:00:02 回复(0)
我是超越迷妹了😘头像 我是超越迷妹了😘
单支树
发表于 2017-09-20 10:54:33 回复(0)
luckychenfan头像 luckychenfan
排除法。例如如下二叉树
                                            C
                                      /
                             A
                                 \
                                     B
先序遍历为：ABC，后序遍历为：CBA，符合题意。显然选项A、B都可以排除；对于选项D，度为2的二叉树，不可能出现先序遍历和后序遍历正好相反的情况（很好验证——画一个只有三个结点的二叉树就可以验证 ），所以D排除。正确答案为C。这是做选择题最快的方法，希望楼主能够采纳，谢谢！
发表于 2016-09-14 16:47:06 回复(3)
Jerry Zhao头像 Jerry Zhao
如果每个节点只存在一个子节点，即结点的度为1，假设A为父节点，B为子节点，无论B为左子树还是右子树，先序均为AB，而后序为BA。即高度为n的话就能满足题目要求。
发表于 2015-08-27 08:37:36 回复(0)
lgllgl头像 lgllgl
不一定是A B这两种情况 但一定是C这种情况 C包含了A B

发表于 2022-08-08 15:32:32 回复(0)
提交观点

问题信息

树
来自：英特尔2016软件类研...
难度：
8条回答 15494浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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