只給出一個遍歷時尋找二叉樹的另外兩個遍歷

Question

我知道當給定它的inorder和preorder遍歷作爲字符串時，你可以重建二叉樹，但只有在僅有的時候才能找到後序和/或預編碼遍歷給中序遍歷？

Answer 1

不，只從中序遍歷檢索後序/前序是不可能的。如果是這樣，就有可能只用中序遍歷來重構二叉樹，這是不可能的，因爲一個序遍歷可以給你幾個可能的重構二叉樹。

Answer 2

你的輸入是怎樣的，樹的目的是什麼？

如果你有一個完全用圓括號表示的有序表達式，那麼你有一棵uniqe樹，並且通過構造樹並從樹中構造前後順序項來獲得前後順序。

如果您的表達沒有完全用括號括起來，那麼這表明在與您的有序順序相匹配的不同樹之間沒有區別。例如，如果它是代表算術表達式的樹，則x+y+z與(x+y)+z和x+(y+z)相同。 但是這意味着，您使用的前置或後置順序並不重要，++xyz和+x+yz也是一樣的。

現在，如果這並不重要，你不需要擔心你的有序的幾個posustible表示。只需選擇其中一個表示，然後計算該樹引發的前後順序。