自动搬运

查看原文

来自洛谷，原作者为

	亦枫 我不知道去向何方，但我已在路上。

搬运于2025-08-24 22:32:04，当前版本为作者最后更新于2021-11-09 18:14:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

题意：给你一棵满二叉树的中序遍历，求原树。特别地，给定 $k$，此树有 $2^k-1$ 个节点。

我们直接取最中间的节点，放到该层，再将左右分为两棵子树，在进行相同的操作即可。

递归解决，答案用二维数组记录，最后一层层依次输出即可。

貌似没什么难点

关键部分Code：

void dfs(int l,int r,int dep){//l表示左端点，r表示右端点，dep表示深度
	if(l>r)return ;//跳出递归的条件
	cnt[dep]++,ans[dep][cnt[dep]]=a[(l+r)/2];//记录答案
	dfs(l,(l+r)/2-1,dep+1);//左子树
	dfs((l+r)/2+1,r,dep+1);//右子树
}