先回顾一下二叉树的前序、中序和后序：
二叉树
前序：VLR
中序：LVR
后序：LRV
假设前序、中序遍历结果如下，开始重建二叉树：
前序序列：[ ABHFDECKG ]
中序序列：[ HBDFAEKCG ]
1、可以确定根节点是A，然后在中序中根据 A 的位置，可以确定 L（HBDF）和 R（EKCG）。取出 A，画出二叉树
重建二叉树-1
2、继续根据前序：VLR，中序：LVR 的规则拆分左子树 L（HBDF）。
左子树的前序：B H F D 中序 ：H B D F ，确认B 为根节点，H为左节点，DF为右节点
重建二叉树-2
3、下面，我们拆分右子树R（EKCG）
右子树 前序：E C K G； 中序： E K C G
我们可以根据前序，确认E为根节点，没有左节点，只有右节点（KCG）
重建二叉树-3
4、继续拆分右子树
右子树前序： C K G； 中序： K C G
我们可以根据前序，确认C为根节点，左节点K，右节点 G
到此二叉树重建完成。
重建二叉树-4
（例子参考自百度经验）
网友评论