只给出一个遍历时寻找二叉树的另外两个遍历

Question

我知道当给定它的inorder和preorder遍历作为字符串时，你可以重建二叉树，但只有在仅有的时候才能找到后序和/或预编码遍历给中序遍历？

Answer 1

不，只从中序遍历检索后序/前序是不可能的。如果是这样，就有可能只用中序遍历来重构二叉树，这是不可能的，因为一个序遍历可以给你几个可能的重构二叉树。

Answer 2

你的输入是怎样的，树的目的是什么？

如果你有一个完全用圆括号表示的有序表达式，那么你有一棵uniqe树，并且通过构造树并从树中构造前后顺序项来获得前后顺序。

如果您的表达没有完全用括号括起来，那么这表明在与您的有序顺序相匹配的不同树之间没有区别。例如，如果它是代表算术表达式的树，则x+y+z与(x+y)+z和x+(y+z)相同。 但是这意味着，您使用的前置或后置顺序并不重要，++xyz和+x+yz也是一样的。

现在，如果这并不重要，你不需要担心你的有序的几个posustible表示。只需选择其中一个表示，然后计算该树引发的前后顺序。