二叉树遍历

题目形容

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

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

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

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

思路：

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

详细分析：

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

        KCDFEGH     B

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

C是左子树，FEGH是右子树

      K  D        BC   FEGH

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

F是左子树，GH是右子树

      K  D        BC    E   F   GH

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

      K  D        BC    E   F   G         H

所以后续遍历为:

C F H G E D B K