如何在给定深度和后序遍历的情况下构建树，然后打印其前序遍历

Question

我需要构造一棵树，给定深度和后序遍历，然后我需要生成相应的前序遍历。示例：

Depth: 2 1 3 3 3 2 2 1 1 0
Postorder: 5 2 8 9 10 6 7 3 4 1
Preorder(output): 1 2 5 3 6 8 9 10 7 4

我定义了两个包含后序序列和深度的数组。之后一直想不出算法来解决

这是我的代码：

int postorder[1000];
int depth[1000];
string postorder_nums;
getline(cin, postorder_nums);
istringstream token1(postorder_nums);
string tokenString1;
int idx1 = 0;
while (token1 >> tokenString1) {
    postorder[idx1] = stoi(tokenString1);
    idx1++;
}
string depth_nums;
getline(cin, depth_nums);
istringstream token2(depth_nums);
string tokenString2;
int idx2 = 0;
while (token2 >> tokenString2) {
    depth[idx2] = stoi(tokenString2);
    idx2++;
}
Tree tree(1);

Answer 1

我不会给你代码，但会给出一些解决问题的提示。

首先，对于后序图处理，您首先访问 children，然后打印（处理）节点的值。因此，树或子树 parent 是其（子）树中处理的最后一件事。我将 10 替换为 0 以获得更好的缩进：

2 1 3 3 3 2 2 1 1 0
--------------------
5 2 8 9 0 6 7 3 4 1

如上所述，深度为 0 的节点或根节点是最后一个。让我们将所有其他节点降低 1 级：

2 1 3 3 3 2 2 1 1 0
-------------------
                  1
5 2 8 9 0 6 7 3 4

现在识别深度为1的所有节点，并降低所有非深度0或1的节点：

2 1 3 3 3 2 2 1 1 0
-------------------
                  1
  2           3 4 
5   8 9 0 6 7

如您所见，(5,2) 在一个子树中，(8,9,10,6,7,3) 在另一个子树中，(4) 是一个 single-node 子树。换句话说，所有在2左边的都是它的子树，所有在2右边和3左边的都在3的子树中，所有在3和4之间的都在4的子树中（这里：空).

现在让我们以类似的方式处理深度 3：

2 1 3 3 3 2 2 1 1 0
-------------------
                  1
  2           3 4 
5         6 7 
    8 9 0

2 是 2 的 parent；
6 是 8、8、10 的 parent；
3 是 parent 6,7;

或非常明确：

2 1 3 3 3 2 2 1 1 0
-------------------
                  1
   /           / /
  2           3 4 
 /         / /
5         6 7 
     / / /
    8 9 0

这就是您可以根据现有数据构建树的方法。

编辑

显然，这个问题可以通过递归轻松解决。在每一步中，您找到最低深度，打印节点，并为其每个子树递归调用相同的函数作为其参数，其中子树通过查找 current_depth + 1 来定义。如果深度传递为另一种说法，它可以省去计算最低深度的必要性。

Answer 2

您实际上可以在不构建树的情况下执行此操作。

首先请注意，如果您反转后序序列，您会得到一种前序序列，但子级以相反的顺序访问。所以我们将使用这个事实并从后到前迭代给定的数组，我们还将在输出中从后到前存储值。这样至少兄弟姐妹的顺序是对的。

因此，我们从输入中获得的第一个值将始终是根值。显然我们不能将这个值存储在输出数组的末尾，因为它确实应该放在第一位。但是我们会将这个值放在堆栈上，直到处理完所有其他值。对于后面跟有“更深”值的任何值，都会发生同样的情况（同样：我们正在以相反的顺序处理输入）。但是一旦我们找到一个不更深的值，我们就会将堆栈的一部分刷新到输出数组中（也是从后向前填充）。

处理完所有值后，我们只需要将堆栈中剩余的值刷新到输出数组中即可。

现在，我们可以在这里优化我们的 space 用法：当我们从后面填充输出数组时，我们在其前面有空闲的 space 用作堆栈 space对于这个算法。这有一个很好的结果，当我们到达终点时，我们不再需要刷新堆栈，因为它已经在输出中，每个值都应该在。

这是该算法的代码，其中我没有包含输入集合，显然您已经在使用它了：

// Input example
int depth[] = {2, 1, 3, 3, 3, 2, 2, 1, 1, 0};
int postorder[] = {5, 2, 8, 9, 10, 6, 7, 3, 4, 1};
// Number of values in the input
int n = sizeof(depth)/sizeof(int);

int preorder[n]; // This will contain the ouput
int j = n; // index where last value was stored in preorder
int stackSize = 0; // how many entries are used as stack in preorder
for (int i = n - 1; i >= 0; i--) {
    while (depth[i] < stackSize) {
        preorder[--j] = preorder[--stackSize]; // flush it
    }
    preorder[stackSize++] = postorder[i]; // stack it
}
// Output the result:
for (int i = 0; i < n; i++) {
    std::cout << preorder[i] << " ";
}
std::cout << "\n";

该算法的 auxiliary space 复杂度为 O(1)——因此不计算输入和输出所需的内存——并且有O(n) 的时间复杂度。

如何在给定深度和后序遍历的情况下构建树，然后打印其前序遍历

How to construct a tree given its depth and postorder traversal, then print its preorder traversal

c++

algorithm

tree

preorder

postorder