毒瘤题 “L2-047 锦标赛” 解法

一个四不像的解法。

输入给出的是两两比较之后“余留”下来的结点，假如我们把这些“余留”下来的结点从叶子向根递推，当访问到某个结点时，可以考虑三种情况：

第一种，该结点比其中一棵子树的最大值小，比另一棵子树的最大值大。我们知道有一个更大的结点通过了这里，所以才余留了当前这个结点，更大的结点一定来自大子树，当前的结点一定来自小子树。

（更大的结点一定来自大子树，当前的结点一定来自小子树，因为大子树中的某处曾“余留”了一个比当前结点大的点，假设当前的结点来自大子树，那么它不可能现在才被“余留”。）

第二种，该结点比任意哪棵子树的最大值大，我们可以假定它来自其中任意一棵子树，那么通过此处的更大的结点就是来自另一棵子树。

（当前结点与它的两棵子树，对于后续的结点来说，又是一棵子树，递归地来看，这种思路仍然可以成立）

第三种，该结点比任意哪棵子树的最大值小，它不可能来自任意哪颗子树，因此是"No Solution"。

对于子树最大值的计算，我们容易知道递推式为：

根据当前结点，推出它在答案数组中可放的区间：

（假定k为叶子所在的最底层，i为当前层，j为当前层的第几个结点）

1，当前结点来自它的左子树：

[ (2 * j) * (1 << k - i - 1), (2 * j + 1) * (1 << k - i - 1) ) （左闭右开）

2，当前结点来自它的右子树：

[ (2 * j + 1) * (1 << k - i - 1), (2 * j + 2) * (1 << k - i - 1) )（左闭右开）

总体代码：