Python:-从给定的inorder遍历返回前序遍历

Question

我正在研究算法问题，偶然发现了以下问题：

Given an inorder traversal of a binary tree, return preorder traversal

例如：-

Inorder - [16, 10, 4, 15, 28]应返回preorder [4, 10, 16, 15, 28]。

我用谷歌搜索了一下，但找不到任何解决方案。如何获得预订单遍历？

Answer 1

考虑以下两个树，它们具有相同的顺序遍历，但不同的预顺序遍历。您提供的输出预序遍历以4开始，这意味着节点4必须是树的根，但是您提供的顺序遍历不能保证以节点4为根的树。

​

​