golang工程师应该会的数据结构与算法反向构造二叉树
@author 汪春波
条件1 .由前序序列为 ABHFDECG 根左右
条件2. 中序序列为 HBED F A GC 左根右
ps 必须有中序序列才可以推出二叉树
第一步
有条件1 知道。根为 A
条件2 知道，左边第一个为 H 。 那么得到了根为A，所以，树的左右为， HBED GC
第二步
那么 我们来看 HBEDF
条件2 知道 左 根 右，推出 B肯定为根节点。按照位置即可推出。
条件1 知道 根左右。 则 B 肯定为左边的。
所以第二层第一个为 B
根据 HBEDF 推出（中序给出结果 左根右边
B 的子节点为，左边肯定为 H，右边为 EDF
第三
由中序,
则 EDF为
D根 ，推测，D 左右为 E F
由 前序，FDE 根左右
得到，F 也为根。
则
结合发现冲突，则排序一下，
D 下面 肯定是 E
F 下面肯定是 D
所以得到
第四 右边
GC
根据 中序，得到 C定为根，G左。
根据前序得到， C定为根，G左。
所以
结果拼起来
关于 LearnKu
粤公网安备 44030502004330号