@[LJ07](/user/312306) @[出言不逊王子](/user/336603) @[Yansuan_HCl](/user/120324) 应该是满二叉树是比较费时间的，我就是不明白满二叉树假如枚举的每一棵子树都有一点不同，那么不就要每一节点都要遍历吗，就N^2了啊,求各位大佬解答
by XSean @ 2023-06-28 22:31:50
@[Sean_xzx](/user/546830)
我之前讲的其实已经很清楚了，所以我再说一遍吧：
满二叉树深度 $O(\log n)$，最坏情况下每一个节点都会被他父亲遍历一遍，所以是 $O(n\log n)$。
或者你理解为每次 check 复杂度为 $O(size)$（$size$ 为子树大小）。那么复杂度就是所有子树大小和 $O(\sum \frac{n}{2^i}*2^i)$，也就是 $O(n\log n)$。
by LJ07 @ 2023-06-28 23:57:31
而不是表面看上去子树大小和为 $O(n^2)$。这是个思维误区。
by LJ07 @ 2023-06-28 23:58:27
@[LJ07](/user/312306) 6啊，谢谢啦
by XSean @ 2023-06-29 07:51:08