P7673 [COCI2013-2014#5] OBILAZAK题解

亦枫 · 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);//右子树
}