java - 从给定的前序输入输出后序二叉搜索树，无需构造树或使用递归

Question

问题描述：（语言为java）

给定一个表示二叉搜索树的前序遍历的输入数组，输出 BST 的后序遍历。

抓住 ：

• 没有构建 BST 节点。
• 没有递归。
• O(n) 运行时间。

我已经尝试了几个小时，但仍然没有任何线索。
最难的部分是不使用树节点结构。
有人有想法吗？

Answer 1

这是一个提示：

在preorder遍历中，数组的第一个元素总是树的根，
所以如果NodeElemnts[]给定数组，那么NodeElemnts[0] 将是树的根

那么，左节点位于 ，2n+1右节点位于2n+2，n是当前数组的索引。

对于前到后：

[root][leftChild][rightChild]（前）-> [leftChild][rightChild][root]（后）.....想想BFS :)