频道栏目
首页 > 考试 > 其他 > 正文

【一天一道LeetCode】#95. Unique Binary Search Trees II

2016-06-18 09:01:34         来源:ZeeCoder  
收藏   我要投稿

(一)题目

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

这里写图片描述

(二)解题

刷了这么久的题,做题起来还是这么吃力,好心塞。
今天这道题想了好久,写完代码发现思路都错了。
明天继续想!
注意!一下是错误代码!!!!!!!!!!!!!!!!!!

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void GetTreeSize(TreeNode* head,int &num)
{
    if (head!=NULL)
    {
        num++;
        GetTreeSize(head->left,num);
        GetTreeSize(head->right,num);
    }
    else return;
}
bool isInTree(TreeNode* head , int tar)
{
    TreeNode* p = head;
    while(p!=NULL)
    {
        if(tar>p->val) p = p->right;
        else if(tarval) p = p->left;
        else return true;
    }
    return false;
}
void dpBSTrees(int& n , int i , vector& isVaild , int count , TreeNode* head,TreeNode* temp, vector& ret)
{
    int size = 0;
    GetTreeSize(head,size);
    if (size==n) {
        ret.push_back(head);
        return;
    }

    bool isleft = false;
    bool isright = false;
    for(int j = i-1 ; j>=1 ; j--)
    {
        if(!isInTree(head,j)) 
        {
            temp->left = new TreeNode(j);
            dpBSTrees(n,j,isVaild,count,head,temp->left,ret);
            isleft= true;
        }
    }
    for(int z = i+1 ; z<=n ; z++)
    {
        if(!isInTree(head,z)) 
        {
            temp->right = new TreeNode(z);
            dpBSTrees(n,z,isVaild,count,head,temp->right,ret);
            isright = true;
        }
    }
    if (isright||isleft)
    {
        temp=NULL;
    }
}

vector generateTrees(int n) {
    vector ret;
    vector isVaild(n+1,true);
    int count = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        TreeNode* head = new TreeNode(i);
        isVaild[i] = false;
        dpBSTrees(n,i,isVaild,count+1,head,head,ret);
        isVaild[i] = true;
    }
    return ret;
}
相关TAG标签 一道
上一篇:bzoj4556【TJOI2016&HEOI2016】字符串
下一篇:NEFU 1132 分层图最短路
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站