algorithm - 构建一棵树

Question

如何根据中序和先序遍历构造一棵树？我只是在寻找一种高效的算法。

Answer 1

来自 Sun's (Oracle now, I guess...) forum 的公然复制和粘贴:

Question:
Can anybody help me on how to construct Binary tree from inorder and postorder traversals,i just want to know the algorithm so that i can apply it.

答案:
设p_1, p_2 ... p_n 为后序遍历并设i_1 , i_2 ... i_n 为中序遍历。从后序遍历我们知道树的根是p_n。在中序遍历中找到这个元素，比如说i_1, i_2 ... i_k-1 p_n i_k+1 ... i_n。中序遍历找到左子树的所有元素，即i_1, i_2 ... i_k-1 和右子树，即 i_k+1 ... i_n 分别。

删除元素 p_n(和元素 i_k == p_n)。在p_1, p_2 ... p_j 中找到最右边的元素p_j >... p_n-1 其中 p_j 是 i_1 中的一个元素，i_2 .. . i_k-1。这是原始树的左子树的根。 拆分p_1, p_2 ... p_j 和p_j+1 ... p_n-1 和 i_1, i_2 ... i_k-1 和 i_k+1 ... i_n。现在你有两个子序列代表原始的两个子树的后序和中序遍历 树。

作者:JosAH .

我已经按照 Jos 的指示实现了该算法，并且效果很好!