面对这种问题时我们该怎么解决?
今天写数据结构题。发现了一道总是碰见问题的题在这里我写了一种求解方法我自己称它为分层递归求解。
第一步通过观察我们知道后序遍历时最后一个是根节点A
在中序序列中A的左边是左子树右边是右子树
第二步我们来画第一层为根节点的右子树为A-C-F
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc29uZ2p1bnlhbg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">
第三步拆分左子树
在中序序列中为DBGE(由于我们不知道左子树中的树结构无法直接看出来就把左子树另外拆分出来看)在后序序列中为DGEB
第五步模仿第一步和第二步的做法来画
这个时候我们能够得到左子树的结构例如以下:
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvc29uZ2p1bnlhbg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">