LeetCode-108. 将有序数组转换为二叉搜索树

雨点打透心脏的1/2处 2023-05-29 03:52 10阅读 0赞

# [108. 将有序数组转换为二叉搜索树][108.] #

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: \[-10,-3,0,5,9\],

一个可能的答案是：\[0,-3,9,-10,null,5\]，它可以表示下面这个高度平衡二叉搜索树：

0
         / \
       -3   9
       /   /
     -10  5

来源：力扣（LeetCode）

## 参考某大神的题解 ##

二叉平衡树的根节点就是数组的中间的那个数，对于子树而言其子树的根节点也是二分后中间的那个数，所以可以递归+二分查找，不断的插入根节点就行。太神奇啦～～～

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution 
    public:
        TreeNode* sortedArrayToBST(vector<int>& nums) { 
            return BST(nums,0,nums.size()-1);
        }
    
        TreeNode* BST(vector<int>& nums,int l,int r) { 
            if(l > r)
                return NULL;
            int mid = (l+r)>>1;
            // 没搞明白为啥这里不能用malloc来分配？？
            TreeNode *Tree = new TreeNode(nums[mid]);
            //Tree->val = nums[mid];
            Tree->left = BST(nums,l,mid-1);
            Tree->right = BST(nums,mid+1,r);
            return Tree;
        }
    };

## 贴下自己写的 ##

虽然不对，但可以建一颗平衡二叉树

#include <iostream>
    #include <cstring>
    #include <cstdlib>
    #include <cstdio>
    #include <vector>
    using namespace std;
    
    struct TreeNode { 
        int val;
        TreeNode *left;
        TreeNode *right;
    };
    void Insert(TreeNode *&p, int k) { 
        if(p == NULL) { 
            p=(TreeNode *)malloc(sizeof(TreeNode));
            p->val = k;
            p->left = p->right = NULL;
        }
        else if(k<p->val)
            Insert(p->left,k);
        else 
            Insert(p->right,k);
    }
    void Divide(TreeNode *&bt, vector<int> &nums,int l, int r) { 
        int mid = (l+r)/2;
        //printf("%d %d %d ",l, r,nums[mid]);
        if(mid < l || mid > r || r < l) { 
            //printf("No\n");
            return;
        } 
        //printf("\n");
        Insert(bt,nums[mid]);
        Divide(bt,nums,l,mid-1);
        Divide(bt,nums,mid+1,r);
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) { 
        TreeNode *Bt;
        Bt=NULL;
        int l = 0, r = (int)nums.size();
        Divide(Bt,nums,l,r-1);
        return Bt;
    }
    void PrintTree(TreeNode *bt) { 
        if(bt!=NULL){ 
            printf("%d ",bt->val);
            PrintTree(bt->left);
            PrintTree(bt->right);
        }
    }
    int main() { 
        vector<int> nums = { -10,-3,2,5,9};
        TreeNode *Bt = sortedArrayToBST(nums);
        PrintTree(Bt);
        printf("\n");
        return 0;
    }

[108.]: https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/