leetcode1008前序遍历构造二叉搜索树

痛定思痛。 2022-09-04 00:40 162阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]  
思考

1.  前序遍历是根左右，而且又是排序树，那么左边的子树必然比根小，右边的子树必然比根大，那么左右子树的边界就好找了
2.  左右子树也是根左右的顺序，递归进行子树建立

#include<stdio.h>
    #include<stdlib.h>
    struct TreeNode { 
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
     };
    
    struct TreeNode* gostart(int start,int end,int *preorder){ 
        if(start>end)
            return NULL;
        struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
        root->val = preorder[start];
        int i;
        for(i=start+1;i<=end;i++)
        { 
            if(preorder[i]>preorder[start])
                break;
        }
        root->left = gostart(start+1,i-1,preorder);
        root->right = gostart(i,end,preorder);
        return root;
    }
    
    struct TreeNode* bstFromPreorder(int* preorder, int preorderSize){ 
        struct TreeNode *root =NULL;
        root = gostart(0,preorderSize-1,preorder);
        return root;
    
    }
    
    int main(){ 
        int  preorder[] = { 8,5,1,7,10,12};
        struct TreeNode *root = bstFromPreorder(preorder,6);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20220829/2af46b9c2d9c428fa1ac54d41e866124.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20220829/719413b250204fa1930466541d961e9d.png