首页 > 代码库 > BST创建

BST创建

思路:把数字排序,排序后数字列,中间点为父节点,左边部分为左子树,右边为右子树。

 

假设节点定义为:

// Definition for binary treestruct TreeNode {   int val;   TreeNode *left;   TreeNode *right;   TreeNode(int x) : val(x), left(NULL), right(NULL) {}};

递归的思路实现:

TreeNode *makeArray2BST(int *a,int len){    TreeNode *t;    if(len == 0)        return NULL;    else if(len == 1)    {        t = new TreeNode(a[0]);    }else if(len == 2){        t = new TreeNode(a[1]);        t->left = new TreeNode(a[0]);    }else{        int n = len/2;        t = new TreeNode(a[n]);        t->left = makeArray2BST(a,n);        t->right = makeArray2BST(a+n+1,len-n-1);    }    return t;}



 

BST创建