中级农民
- 积分
- 128
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2011-2-8
- 最后登录
- 1970-1-1
|
所求的BST必须是完整的子树。对每个节点,分别求左右两边最大的BST,如果恰好是两边子树,则检查是否能与该节点构成更大的BST,能则返回本身,不能则返回左右两边更大的那个。需要用变量保存两边子树中最大BST的数值的上下界以及size。欢迎指出bug。
- struct node
- {
- int v;
- node *left, *right;
- node(int val = 0) : left(NULL), right(NULL), v(val) {}
- };
- node *checkBST(node *root, int &l, int &r, int &sz)
- {
- if(!root) return NULL;
- int ll, lr, rl, rr, s1, s2;
- ll = lr = rl = rr = root->v;
- s1 = s2 = 0;
- node *nl = checkBST(root->left, ll, lr, s1);
- node *nr = checkBST(root->right, rl, rr, s2);
- if(nl == root->left && nr == root->right) {
- if(lr <= root->v && root->v <= rl) {
- sz = s1+s2+1;
- l = ll; r = rr;
- return root;
- }
- }
- sz = max(s1, s2);
- return s1>s2?nl:nr;
- }
- node *findMaxBST(node *root, int &sz)
- {
- int l, r;
- return checkBST(root, l, r, sz);
- }
复制代码 |
|