【C++】根据遍历确定二叉树

已知中序遍历和先序遍历可以唯一确定一棵二叉树，因为根结点是先序遍历的第一个结点，我们只要在中序遍历中找到根结点的位置，就能划分左右子树。然后递归地处理左右子树，就能唯一构建一棵二叉树。
同理已知中序遍历和后序遍历也能唯一确定一棵二叉树。
但是已知先序遍历和后序遍历不能唯一确定一棵二叉树，反例如下：

左右两棵树的先序遍历都为1 2，后序遍历都为2 1，但不相同。

已知先序遍历和中序遍历求二叉树的方法如下
设先序遍历
$7143265$
中序遍历为
$1342756$

根据啊先序遍历确定根节点是7，根据中序遍历确定左子树有1,3,4,2，右子树有5,6
根据先序遍历确定根节点是1的子树，根据中序遍历确定左子树没有，右子树有3,4,2
根据先序遍历确定根节点是4的子树，根据中序遍历确定左子树是3，右子树是2
根据先序遍历确定根节点是6的子树，根据中序遍历确定左子树是5，没有右子树

其中a数组是中序遍历，b数组是先序遍历

// a数组为中序遍历，b数组为先序遍历
// x1、y1为当前子树在a数组中下标的范围，x2为前子树在b数组中下标的起点
int a[N], b[N], son[N][2];
void dfs(int x1, int y1, int x2) {
   int pos = x1;
   while (a[pos] != b[x2]) { // 在中序遍历里找到当前子树的根
       pos++;
   }
   int len1 = pos - x1, len2 = y1 - pos; // 在中序遍历里确定当前子树的左子树和右子树大小
   if (len1 > 0) { // 如果有左子树，那么根据先序遍历确定这个节点的左孩子
       son[b[x2]][0] = b[x2 + 1];
       dfs(x1, pos - 1, x2 + 1); // 递归进入左子树
   }
   if (len2 > 0) { // 如果有右子树，那么根据先序遍历确定这个节点的右孩子
       son[b[x2]][1] = b[x2 + 1 + len1];
       dfs(pos + 1, y1, x2 + 1 + len1); // 递归进入右子树
   }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19