已知二叉树前序和中序求后序

希赛网 2023-11-11 17:14:23

在二叉树问题中，掌握二叉树的三种遍历方式（前序遍历、中序遍历和后序遍历）是至关重要的。在某些情况下，需要通过给定的前序和中序遍历顺序来确定二叉树，并且需要求其中序遍历的结果。

本文将从多个角度分析如何已知二叉树前序和中序求后序。在分析之前，我们需要了解什么是前序遍历、中序遍历和后序遍历。

前序遍历是指先访问当前节点然后访问它的左子树和右子树，中序遍历是指先访问左子树，然后访问当前节点，再访问右子树，后序遍历是指先访问左、右子树，最后访问当前节点。因此，我们可以通过前序和中序遍历来唯一确定树的结构，然后通过这个结构来获取后序遍历。

第一种解法：递归

利用前序遍历确定根节点，然后在中序遍历中找到根节点的位置，从而可以确定左子树和右子树的大小。接下来，我们可以递归地寻找左子树和右子树的后序遍历，并最终将它们拼接在一起，得到整个树的后序遍历。

具体实现方式为，我们定义一个递归函数，该函数的输入参数为前序遍历序列、中序遍历序列和序列长度，输出参数为后序遍历序列，该函数可具体实现如下：

```

vector getPostOrder(vector & preorder, vector & inorder, int n) {

if (n == 0) return {};

if (n == 1) return {preorder[0]};

vector postorder;

int root = preorder[0], i = 0;

while (inorder[i] != root) i++;

vector left_pre(preorder.begin()+1, preorder.begin()+i+1);

vector left_in(inorder.begin(), inorder.begin()+i);

vector right_pre(preorder.begin()+i+1, preorder.end());

vector right_in(inorder.begin()+i+1, inorder.end());

vector left_post = getPostOrder(left_pre, left_in, i);

vector right_post = getPostOrder(right_pre, right_in, n-i-1);

postorder.insert(postorder.end(), left_post.begin(), left_post.end());

postorder.insert(postorder.end(), right_post.begin(), right_post.end());

postorder.push_back(root);

return postorder;

}

```

第二种解法：栈遍历

我们可以使用已知的前序和中序遍历，以及一个栈来计算后序遍历。不断将前序序列中的元素压栈，判断当前栈顶元素在中序序列中的位置，如果当前节点在中序序列的位置在栈顶节点右边，我们需要从栈中弹出元素，直到当前节点的位置在栈顶元素的左侧。接下来，我们将当前节点压入栈中，并移动到其右子树。重复上述步骤，直到所有节点都被访问。

代码实现：

```

vector getPostOrder(vector & preorder, vector & inorder) {

vector postorder;

stack s;

int j = 0;

for(int i = 0; i < preorder.size(); i++){

int x = preorder[i];

while(!s.empty() && s.top() == inorder[j]){

postorder.push_back(s.top());

s.pop();

j++;

}

s.push(x);

}

while(!s.empty()){

postorder.push_back(s.top());

s.pop();

}

return postorder;

}

```

第三种解法：数组模拟栈遍历

由于第二种解法中需要维护一个栈，因此我们可以尝试使用数组来模拟栈。在这种情况下，我们可以通过维护一个栈顶指针来模拟栈的操作。数组的下标表示节点编号，每个节点有left_child和right_child两个指针，分别表示它的左孩子和右孩子。我们需要将前序和中序遍历转换为树结构，然后按照后序遍历的顺序遍历整个树。

具体实现方式如下：

```

struct Node {

int left_child, right_child;

Node(): left_child(-1), right_child(-1) {}

};

vector getPostOrder(vector & preorder, vector & inorder) {

int n = preorder.size();

vector tree(n);

vector vis(n, false);

stack s;

for(int i = 0; i < n; i++){