# 求二叉树的遍历

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

输入描述:

两个字符串，其长度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: 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:

```
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>
```

The question should be specific, self-contained, and written in natural language.
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.