Question

请问二叉树遍历问题？

二叉树的先序遍历和中序遍历如下：
先序遍历：ABDFHCEGI
中序遍历：BFHDAEIGC
请问 二叉树的结构形状？

Answer 1

A
/ \
B C
\ /
D E
/ \
F G
\ /
H I
解决这类问题可以这么想：
先序遍历是 根、左、右，即先访问根结点、再访问左结点、然后是右结点。所以A就是这个二叉树的根结点、B就是第一左子树的根结点...。然后结合中序遍历结果BFHDAEIGC，可以看到BFHD和EIGC在A的两边，这时就知道BFHD和EIGC分别是以A为根结点的左子树元素和右子树元素。然后依次对BFHD和EIGC再做相同的处理，循环做这样的处理就可以得到这个二叉树的结构形状。

Answer 2

A左孩子B
右孩子C
B右孩子D
D左孩子F
F右孩子H

C左孩子E
E右孩子G
G左孩子I