由于有结构比较上的剪枝，因此最坏情况就是满二叉树和完全二叉树。这个时候判断的次数是 $O(logn)$ 层的。因此总的复杂度就是 $O(nlogn)$。
by Naitoah @ 2022-09-05 20:35:27
@[hy233](/user/259300) 我看了一下我贺的代码，剪枝 `siz[i]>ans` 保证了：
若当前 `check` 的与答案子树不交，则复杂度为 $T(n)$；`check` 的包含答案子树，则 `siz` 至少是 `2*ans+1`。
by Yansuan_HCl @ 2022-09-05 20:40:41
@[hy233](/user/259300) 这样 `check` 的大小只会翻倍 $O(\log n)$ 次？
by Yansuan_HCl @ 2022-09-05 20:41:22
@[Naitoah](/user/284054) @[Yansuan_HCl](/user/120324) 谢谢大佬！
by hy233 @ 2022-09-05 20:42:50
@[Yansuan_HCl](/user/120324) tql%%%
by hy233 @ 2022-09-05 20:42:58
@[hy233](/user/259300) 我的代码是记录当前对称的左根和右根，一次向下一层，最多 $\log n$ 层
by 出言不逊王子 @ 2022-09-05 20:43:58
@[hy233](/user/259300) 本题的复杂度最坏事实上是满二叉树的情况（感性理解）。
满二叉树每向儿子走一步，子树大小缩小 $1/2$（否则是可以提前判掉的），所以复杂度是 $O(n\log n)$。（或者认为 check 是将每个点向上跳到根节点的次数之和）然后复杂度就是 $\sum \frac{n}{2^i}*2^i \le n\log n$。
不过好像晚了
by LJ07 @ 2022-09-05 20:45:05
$2^i\le n$
by LJ07 @ 2022-09-05 20:45:32
@[LJ07](/user/312306) @[出言不逊王子](/user/336603) 没有关系，你们都薄纱我，比我小又比我强，呜呜呜
by hy233 @ 2022-09-05 20:46:57
别假了别假了，sto hy orz
by LJ07 @ 2022-09-05 20:58:51