首页 > 试题广场 >

已知二叉树的先序遍历序列为ABCDEFI，中序遍历序列为CB

[单选题]
已知二叉树的先序遍历序列为ABCDEFI，中序遍历序列为CBDAEFI，则该二叉树的高度为?（树的根结点高度为1） 
  • 2
  • 3
  • 4
  • 5
添加回答
推荐
c++爱上java头像 c++爱上java
根据朱战立 的第四版 数据结构里面这么定义：
结点的层次：从根节点到树中某结点所经路径上的分支数即为该结点的层次。（即从该结点到根节点的边数为该节点的层次数），规定根结点的层次为0。（即根结点的层次为0）。
树的深度：树中所有结点的层次中的最大值称为该树的深度。

依据上面的定义，那么只有一个根结点的二叉树，其深度为0。
在有的书上（例如在百度百科上）规定根结点的深度为1，所以不同书上是不一样的。这个题可能不严谨。

而树的高度没有定义，一般规定根结点的高度为1。所以本题应该为4。

编辑于 2018-05-08 15:28:10 回复(0)
一吻以谢天下头像 一吻以谢天下
通过给定的先序和中序构建二叉树即可：
-- NORMAL --
      A 
   B     E 
C   D     F 
                I
再就是注意，这里说的是树的高度，也就是从根到叶子节点的最长的一条路径上边的条数。所以是3。答案没错，还有不明白的去百度一下树的深度和树的高度的区别即可。
发表于 2018-03-02 21:36:49 回复(1)
GrantLeung头像 GrantLeung
       A
   B     E
C   D     F
                I
高度应该为4吧？
 
发表于 2018-02-22 16:27:49 回复(3)
LJY114头像 LJY114
答案错了，应该是4
发表于 2018-02-22 12:59:19 回复(0)
如风918头像 如风918
发表于 2019-04-08 20:43:53 回复(0)
huangye头像 huangye
答案错误吧，应该是4啊
发表于 2018-04-07 12:40:23 回复(0)
提交观点

问题信息

算法工程师 2018 蘑菇街
上传者：小小
难度：
6条回答 1869浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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