已知一棵二叉树，如果先序遍历的节点顺序是（ KDCEFGHB, 中序遍历是： CDFEGHKB, 则后续遍历结果为（））
二叉树遍历
题目描述
（单选）已知一棵二叉树，如果先序遍历的节点顺序是： KDCEFGHB, 中序遍历是： CDFEGHKB, 则后续遍历结果为（）
- [ ] A. CFHGEBDK
- [ ] B. CDFEGHBK
- [ ] C. FGHCDEBK
- [x] D. CFHGEDBK
- 先序： （根 左 右） 根优先
- 中序： （左 根 右） 根中间
- 后序： （左 右 根） 根最后
- 先确定根节点
- 在确定左子树和右子树
2.1 从左子树中找到左子树的根，回到步骤1
2.2 从右子树中找到右子树的根, 回到步骤1 - 直至查找完，建立树
那么中序遍历中K的俩边分别是左子树和右子树；
左子树为 CDFEGH 右子树为B
K
CDFEGHB左子树中先序遍历为 DCEFGH 中D在最前面，所有D是左子树的根；
C是左子树，FEGH是右子树
K
DB
CFEGHFEGH子树中，先序遍历是EFGH, 所有E是子树根
F是左子树，GH是右子树
K
DB
CE
FGHGH子树中，先序遍历GH, 所以G是根，H是右子树
K
DB
CE
FG
H所以后续遍历为:
【已知一棵二叉树，如果先序遍历的节点顺序是（ KDCEFGHB, 中序遍历是： CDFEGHKB, 则后续遍历结果为（））】C F H G E D B K
推荐阅读
- java中如何实现重建二叉树
- ［原创］能见沂山一棵树，胜读十年无用书！
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- 哥们的诗，好气魄
- 我们就是一棵树（刘建丛）
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- 一棵树，长满一场生涯
- LeetCode-102.|LeetCode-102. 二叉树的层序遍历
- 331.|331. 验证二叉树的前序序列化
- 先序遍历 中序遍历 后序遍历 层序遍历