首页 > 代码库 > 已知二叉树的中序序列为DBGEAFC,后序序列为DGEBFCA,给出对应的二叉树

已知二叉树的中序序列为DBGEAFC,后序序列为DGEBFCA,给出对应的二叉树

面对这样的问题时我们该怎么解决?

今天写数据结构题,发现了一道总是碰见问题的题在这里我写了一种求解方法我自己称它为分层递归求解。

第一步通过观察我们知道后序遍历时最后一个是根节点A

在中序序列中A的左边是左子树右边是右子树

第二步我们来画第一层为根节点的右子树为A-C-F


第三步拆分左子树

在中序序列中为DBGE(因为我们不知道左子树中的树结构无法直接看出来就把左子树另外拆分出来看)在后序序列中为DGEB

第五步模仿第一步和第二步的做法来画

这个时候我们可以得到左子树的结构如下: