首页 > 试题广场 >

某二叉树,其度为n1,度为2的节点数为n2,且先序遍历和后序

[单选题]
某二叉树,其度为1的节点数为n1,度为2的节点数为n2,且先序遍历和后序遍历序列正好相反,则此二叉树的深度为()
  • 2*n1+n2+1
  • n1+n2
  • n1+2*n2+1
  • 2*n1+n2
推荐
先序遍历是M-L-R,后序遍历顺序是:L-R-M,所以只有中间节点顺序变化了,左右节点位置不变,因此这个树的高度一定等于其节点数,总结点数为N1 + 2N2 + 1
所以C
编辑于 2019-09-26 14:30:54 回复(3)
每一层只有一个节点
发表于 2020-04-20 16:33:03 回复(0)
我觉得没有正确答案!
既然先序遍历和后序遍历相反,说明不存在左子树或不存在右子树,而且树的高度等于其节点数,那么说明不存在度为2的结点,从而推出n2=0,这道题就变换为求度为1或度为0的节点数。即n1+n0=n1+n2+1=n1+1。
发表于 2019-10-29 09:43:54 回复(4)

前序和后序相反,说明是一条链表(只有左结点或者只有右结点),因此深度就是结点数。

度为1的结点数为n1,度为0的结点数为1(唯一的叶子),所以答案是n1 + 1。

因为度为2的结点数为0,所以C选项符合答案。

发表于 2021-04-24 15:51:10 回复(1)
把树的度和图的度概念搞混了😂
发表于 2022-10-26 22:38:38 回复(0)
且先序遍历和后序遍历序列正好相反,那么只能是只有左子树,或者只有右子树的二叉树。
所以这类数的结点只有:n0  和n1.且n0=1,n2=0
那么,树的深度可以表示为n1+1
结合答案,选c

发表于 2022-04-05 16:11:48 回复(0)
个人觉得此题 n2 = 0;

但是有两个思路:
思路一:因为先序遍历和后序遍历的顺序相反,可以轻易得出二叉树的高度与结点数n相同,n = n1 + 2 * n2 + 1

思路二:其实可以推出 n2 = 0,所以说题目中的答案应为 n1 + 1 更为合适,但是其实把 n2 = 0 代入思路一中的式子,计算结果是一样的
发表于 2022-03-08 10:36:32 回复(0)
按道理来说是没有正确答案,因为前序和后序相反意味着该树要么没有左子树要么没有右子树,所以树高应该为n1+1,此时n2=0,刚好c答案的计算结果是符合这个的,所以选C,但是就表达式而言没有正确答案
发表于 2021-12-30 19:18:24 回复(0)
特殊值法,秒
发表于 2021-12-01 00:12:42 回复(0)
我不太懂😂
二叉树的度不是小于等于2吗?如果按照题目来说,n1=1了,它的深度只能有2吗?
x小白求解答
发表于 2021-03-19 21:01:24 回复(1)
先序遍历是M-L-R,后序遍历顺序是:L-R-M,所以只有中间节点顺序变化了,左右节点位置不变,因此这个树的高度一定等于其节点数,总结点数为N1 + 2N2 + 1
发表于 2021-03-19 19:33:41 回复(0)
选C
先序遍历是M-L-R,后序遍历顺序是:L-R-M,所以只有中间节点顺序变化了,左右节点位置不变,因此这个树的高度一定等于其节点数,总结点数为N1 + 2N2 + 1
所以C

编辑于 2020-07-07 11:57:59 回复(0)