#95 Unique Binary Search Trees II

本篇文章主要介绍了" #95 Unique Binary Search Trees II"，主要涉及到方面的内容，对于其他编程jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播感兴趣的同学可以参考一下： 一天一道LeetCode本系列文章已全部上传至我的github，地址：ZeeCoder‘s Github 欢迎大家关注我的新浪微博，我的新浪微博 欢迎转载，转载...

一天一道LeetCode

本系列文章已全部上传至我的github，地址：ZeeCoder‘s Github
欢迎大家关注我的新浪微博，我的新浪微博
欢迎转载，转载请注明出处

（一）题目

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);
    }
    elsereturn;
}
bool isInTree(TreeNode* head , int tar)
{
    TreeNode* p = head;
    while(p!=NULL)
    {
        if(tar>p->val) p = p->right;
        elseif(tarval) p = p->left;
        elsereturntrue;
    }
    returnfalse;
}
void dpBSTrees(int& n , int i , vector<bool>& 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<bool> 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;
}

').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('

').text(i)); }; $numbering.fadeIn(1700); }); });

以上就介绍了 #95 Unique Binary Search Trees II，包括了方面的内容，希望对其他编程jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播有兴趣的朋友有所帮助。

本文网址链接：http://www.codes51.com/article/detail_1741919.html