中序遍历和前序遍历确定⼀棵⼆叉树（笔算）
已知前序遍历序列和中序遍历序列，可以唯⼀确定⼀棵⼆叉树。
已知后序遍历序列和中序遍历序列，可以唯⼀确定⼀棵⼆叉树。
但是已知前序遍历序列和后序遍历序列，是不能确定⼀棵⼆叉树的。
下⾯例⼦通过前序遍历和中序遍历确定唯⼀的⼀棵⼆叉树。
前序遍历：EACBDGF
中序遍历：ABCDEFG
1、⾸先根据前序遍历出根节点是E，然后根据中序遍历可以知道ABCD是E的左⼦树，FG是E的右⼦树。
2、然后根据左⼦树的先序：ACBD，中序：ABCD，确定A为根结点，⽆左⼦树，右⼦树为BCD
3、右⼦树为BCD，先序：CBD，中序：BCD，确定C为根结点，B为左⼦树，右⼦树为D
4、右⼦树为GF，先序：GF，中序：FG，确定G为根结点，⽆左⼦树，右⼦树为F
5、最终的⼆叉树为：
后序遍历为：BDCAFGE
后序遍历序列和中序遍历序列，可以唯⼀确定⼀棵⼆叉树和前中很相似，先根据后序遍历的最后⼀个元素确定根结点，然后通过中序遍历分为左右⼦树，再在⼦树确定根结点，以此类推。
试试你学会了吗？
先序：ABJDECFGHI
中序：JBEDAFHGIC
求后序遍历
先序中序后序遍历二叉树
答案：
JEDBHZGFCA
View Code

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。