binary-tree - 通过后序遍历结果恢复一棵二叉树

Question

我可以仅从排序的数组中恢复整个二叉树（count（vertices）= 2^n-1），就好像我进行了后序遍历一样？

我建议的算法很简单，只是为了进行后序遍历：

1. 向左走
2. 向右走
3. current_vertex = 数组[i++]; // 初始化 i = 0

那应该做的工作，不是吗？

Answer 1

不，你不能转换为不止一个post order array二叉树，它们不一样，不可能知道哪一棵是原始的。binary tree

例子-

Post order'd 数组2 3 5可以转换为许多树，例如-

2        // 3 is right child of 2 and 5 of 5
  3
    5

或者

  5     //2 is left child and 3 is right child of 5
2   3