> For the complete documentation index, see [llms.txt](https://mm.ricky.moe/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mm.ricky.moe/algorithm/algorithm-and-data-structure/er-cha-shu-zhuan-ti/qiu-er-cha-shu-de-bian-li.md).

# 求二叉树的遍历

给定一棵二叉树的前序遍历和中序遍历，求其后序遍历

输入描述:

两个字符串，其长度n均小于等于26。 第一行为前序遍历，第二行为中序遍历。 二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

输出描述:

输入样例可能有多组，对于每组测试样例， 输出一行，为后序遍历的字符串。

样例：

```
输入
ABC
BAC
FDXEAG
XDEFAG

输出
BCA
XEDGAF
```

### 思路 <a href="#si-lu-2" id="si-lu-2"></a>

和上面题目的思路基本相同

* 前序遍历找到根结点`root`
* 找到`root`在中序遍历的位置 -> 左子树的长度和右子树的长度
* 截取左子树的中序遍历、右子树的中序遍历
* 截取左子树的前序遍历、右子树的前序遍历
* 递归拼接二叉树的后序遍历

## 实现

```javascript
let pre;
let vin;
 
while((pre = readline())!=null){
  vin = readline();
  print(getHRD(pre,vin));
}
 
function getPostOrder(pre, vin) {
  if (!pre) {
    return '';
  }
  if (pre.length === 1) {
    return pre;
  }
  const head = pre[0];
  const splitIndex = vin.indexOf(head);
  const vinLeft = vin.substring(0, splitIndex);
  const vinRight = vin.substring(splitIndex + 1);
  const preLeft = pre.substring(1, splitIndex + 1);
  const preRight = pre.substring(splitIndex + 1);
  return getPostOrder(preLeft, vinLeft) + getPostOrder(preRight, vinRight) + head;
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://mm.ricky.moe/algorithm/algorithm-and-data-structure/er-cha-shu-zhuan-ti/qiu-er-cha-shu-de-bian-li.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.