從給定的遍歷中恢復樹

Question

如果我們已經提供了有序和預定序，或者有序和後序遍歷，那麼我們是否可以恢復任何類型的樹？例如二叉搜索樹（BST），完整的樹，滿樹，一般二叉樹

Answer 1

是在順序和二叉樹的前序遍歷。

例如，與按順序L1 = [4,2，3，5，1]和預順序L2 = [3，2，4，1，5]：

1. 的根是3（預訂的第一個元素）
2. 左子樹的有序遍歷是[4，2]（L1中的3之前的元素），並且左子樹的預序遍歷是[ 2，4]（必須使用與按序相同的元素）
3. 遞歸地查找左子樹和類似的右子樹。

沒有預購和訂購。

具有兩個頂點的兩個可能的樹具有相同的前序遍歷和後序遍歷。