首页 > 试题广场 >

二叉树的中序遍历为[5,4,1,2,3,6]，后序遍历为[4

[单选题]
二叉树的中序遍历为[5,4,1,2,3,6]，后序遍历为[4,5,2,6,3,1]，新建平衡二叉树，按二叉树的前序遍历顺序将元素插入到平衡二叉树中，对于得到的平衡二叉树说法不正确的是（） 
  • 有3个叶子结点
  • 度为1的结点只有结点5
  • 前序遍历为[4,2,1,3,6,5]
  • 后序遍历为[1,3,2,6,5,4]
查看正确选项
添加回答
数学汤家风头像 数学汤家风

考研党狂喜。

一、 根据中、后序列还原二叉树。
后序序列从后往前看决定根，中序列位置划分左右子树

      1
   /    \  
(5,4) (2,3,6)

    1
   / \
(5,4) 3
     / \
    2   6

    1
   /  \
  5    3
   \  / \
    4 2  6    

二、二叉树先序遍历，根左右

1 5 4 3 2 6

三、构建 AVL
AVL 左右高度差不超过 1

1               4
 \             /  \
  5    RL     1    5
 /
4

  4             4
 / \           / \
1   5         2    5
 \           / \   
  3    RL   1   3
 /
2

    4
   / \
  2   5
 / \   \
1   3   6

A B 显然对
先序：4 2 1 3 5 6
后序：1 3 2 6 5 4
所以选 C
​
发表于 2022-02-09 20:04:57 回复(2)
牛客260047603号头像 牛客260047603号
通过中序，后序确定原树的前序：154326
然后构建平衡树：
4 (2 (1 3)) (5 (NULL 6))
所以前序应该是 421356
发表于 2021-04-10 16:54:15 回复(2)
Elaine_cc头像 Elaine_cc
个人解法，欢迎大家交流批评
发表于 2021-10-17 16:10:42 回复(2)
牛客345731702号头像 牛客345731702号
发表于 2022-03-22 14:55:24 回复(0)
wfl666头像 wfl666
后序遍历：左节点，右节点，根。 中序遍历：左结点，根，右节点。 前序遍历：根，左结点，右节点。
发表于 2022-01-15 12:44:45 回复(1)
陪你一起头像 陪你一起
4 2 5 1 3 6 构建的平衡二叉树为这个
发表于 2021-09-13 10:58:39 回复(0)
牛客JYK头像 牛客JYK
感觉选B啊
发表于 2021-08-22 15:54:07 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试开发工程师 测试工程师 2021 牛客 Java工程师
来自：【2021】牛客模考C...
上传者：小小
难度：
7条回答 2499浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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