Leetcode 1008. 前序遍历构造二叉搜索树（DAY 8）

原题题目

闲谈

最近发现其实用很多解法解出来还是挺简单的
但是真的需要用 时间空间复杂度相对简单的方法做出来确实
另一种世界了
所以最近可能做题会做的比较少
但是每道题都希望能够用最好的方法 时空复杂度最小的做出来

代码实现1（先序+中序）（首刷半看半自解）

//时间复杂度 NlogN 快排 空间复杂度N 中序
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/int* temppreorder;int cmp(const void* a,const void* b)
{
    return (*(int *)a - *(int *)b); 
}struct TreeNode* buildtree(int* inorder,int left,int right)
{
    if(left > right)return NULL;int i;for(i=left;i<=right;i++){
    if(inorder[i] == (*temppreorder))break;}temppreorder++;struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = inorder[i];root->left = buildtree(inorder,left,i-1);root->right = buildtree(inorder,i+1,right);return root;
}struct TreeNode* bstFromPreorder(int* preorder, int preorderSize){
    int i;int* inorder = (int*)malloc(sizeof(int) * preorderSize);memcpy(inorder,preorder,sizeof(int) * preorderSize);qsort(inorder,preorderSize,sizeof(int),cmp);struct TreeNode* root;temppreorder = preorder;root = buildtree(inorder,0,preorderSize-1);return root;
}

代码实现2（递归DFS）

/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/struct TreeNode* visit(struct TreeNode* root,int data)
{
    if(!root){
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = data;root->left = NULL;root->right = NULL;return root;}else if(data > root->val) root->right = visit(root->right,data);else root->left = visit(root->left,data);return root;
}struct TreeNode* bstFromPreorder(int* preorder, int preorderSize){
    int i;struct TreeNode* root = NULL;for(i=0;i<preorderSize;i++)root = visit(root,preorder[i]);return root;
}