二叉树遍历

题目形容

（单选）已知一棵二叉树，如果先序遍历的节点程序是：KDCEFGHB, 中序遍历是：CDFEGHKB, 则后续遍历后果为（）

• [] A. CFHGEBDK
• [] B. CDFEGHBK
• [] C. FGHCDEBK
• [x] D. CFHGEDBK

树遍历规定：(按根的地位记忆)

• 先序：（根 左 右）根优先
• 中序：（左 根 右）根两头
• 后序：（左 右 根）根最初

思路：

1. 先确定根节点
2. 在确定左子树和右子树
   2.1 从左子树中找到左子树的根，回到步骤 1
   2.2 从右子树中找到右子树的根, 回到步骤 1
3. 直至查找完，建设树

详细分析：

先序遍历第一个肯定是树根, 那么 K 为根；
那么中序遍历中 K 的俩边别离是左子树和右子树；
左子树为 CDFEGH 右子树为 B

        K
CDFEGH     B

左子树中先序遍历为 DCEFGH 中 D 在最后面，所有 D 是左子树的根；

C 是左子树，FEGH 是右子树

      K
  D        B
C   FEGH

FEGH 子树中，先序遍历是 EFGH, 所有 E 是子树根

F 是左子树，GH 是右子树

      K
  D        B
C    E
   F   GH

GH 子树中，先序遍历 GH, 所以 G 是根，H 是右子树

      K
  D        B
C    E
   F   G
         H

所以后续遍历为:

C F H G E D B K