某二叉树结点的中序序列为A、B、C、D、E、F、G、H，后序_人人网笔试题

推荐

不眠的风云

B

由后序序列知E为根节点，再由中序遍历知左子树为ABCD，右子树为FGH

由后序遍历BDCA知，A为BDC父节点，BDC为右子树，其中C为BD父节点，B为C的左孩子，D为C右孩子，该树左半部分完成

由中序序列和后序序列知FGH序列不变，则H的左孩子为G，G的左孩子为F，H为E的右孩子，该树可知其层次次序序列为EAHCGBDF,故选B

编辑于 2015-02-03 20:24:03 回复(0)

贪I狼

#

第 1 次：划分左右子树，根据后序遍历可知根节点为 E，然后根据中序遍历划分左右子树

后：[B、D、C、A] [F、G、H] E

中：[A、B、C、D] E [F、G、H]

# 第 2 次：对于根节点 E 的左子树，得 A 节点只有右子树

后序：[B、D、C] A

中序：A [B、C、D]

# 第 3 次：对根节点 A 的右子树，得其右子树根节点为 C ，左子节点为 B，右子节点为 D

后序：[B] [D] C

中序：[B] C [D]

# ...，对 E 的右子树处理同上，最终可以还原出一棵树，得出结果为 B

发表于 2017-03-18 17:16:16 回复(0)

已注销

E

/ \

A H

\ /

C G

/ \ /

B D F

编辑于 2017-04-02 12:29:08 回复(7)

大山猫

发表于 2019-03-19 12:24:10 回复(0)

hjy000

后序遍历和中序遍历为啥起点不一样呢

发表于 2019-10-12 14:22:22 回复(0)

CHN_ByteDance

由后序序列得出根为E，由中序序列得出E的左子树有4个结点，右子树有3个节点。两个序列结合推出根的右子树为： H ↙ F ↘ G 这样在层序遍历序列里，由于从上往下一层一层遍历，H必定先于F，G遍历出来，也就是H出现在F，G的左边，排除法选 B。

发表于 2016-04-10 00:45:39 回复(0)

幻影迷风

该二叉树对应的树林结点的

这题有问题吧，按道理是不应该有E的，说好的是森林

发表于 2015-08-28 17:59:00 回复(0)

某二叉树结点的中序序列为A、B、C、D、E、F、G、H，后序