二叉树的前中后序遍历

秋招记录

二叉树的遍历是笔试常见的题目了，记录一下一劳永逸

对一棵二叉树进行遍历，我们可以采取3种顺序进行遍历，分别是前序遍历、中序遍历和后序遍历。
这三种方式是以访问父节点的顺序来进行命名的。
假设父节点是N，左节点是L，右节点是R，那么对应的访问遍历顺序如下：
前序遍历：中左右 N>L>R
中序遍历：左中右 L>N>R
后序遍历：左右中 L>R>N
总结：
1.先左后右是一定的，父节点的位置决定了前中后
2.利用前序遍历可以得到根节点，就是第一个
3.利用后序遍历可以得到根节点，最后一个
4.确认了根节点，利用中序遍历可以得到左子树和右子树
5.对左子树和右子树分别做前面3点的分析和拆分，相当于做递归，我们就可以重建出完整的二叉树

例题：前序遍历的顺序是: CABGHEDF 中序遍历的顺序是: GHBACDEF

第一步：根节点是C 左包括 GHBA 右包括 DEF

关键：
**记住前中后序所对应的节点遍历顺序！
前中后是指N的位置，左右不变！**