问题描述

一道关于二叉树的编程题

给出一组整数对 { (a[0], b[0]), (a[1], b[1]) ... (a[n-1], b[n-1]) }，所有 a 值 和 b 值分别不重复（任意 i != j 满足 a[i] != a[j] 且 b[i] != b[j]）。构造一棵 n 结点的二叉树，将这 n 个整数对分配到各个结点上。根和所有子树满足以下条件：
1) 所有结点的 a 值满足二叉查找树的顺序，即 left->a < root->a && root->a < right->a；
2) 所有结点的 b 值满足最大堆的顺序，即 root->b > left->b && root->b > right->b。

问题一：实现 build 函数，输入 n 个整数对，返回一棵构造好的二叉树。
struct pair_t {
int a, b;
};
struct node_t {
int a, b;
node_t left, *right;
};
node_t build(pair_t* pair, int n);

例如，输入是 {(5, 8), (2, 10), (4, 3), (1, 5), (0, 2), (9, 1)}，输出是下列二叉树：

提示：1) 构造出的二叉树的形态是存在且唯一的。 2) 想办法确定树根。

问题二：已知满足上述条件的二叉树，设计算法实现插入一个整对 (a, b)，使新的二叉树仍满足上述条件。该算法比较复杂，候选人只需描述思路。

解决方案

是阿里的笔试题吗？？？？