将有序数组转化为平衡的二叉搜索树

柔光的暖阳◎ 2023-10-06 08:14 1阅读 0赞

## 将有序数组转化为平衡的二叉搜索树 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]

#### 思路： ####

###### 分治递归： ######

若树是平衡的二叉搜索树，则根的左右子树均为平衡的二叉搜索树

递归函数的功能为生成以有序数组中间元素为根的平衡二叉搜索树（参数为有序数组，返回根节点），则中间元素左侧的元素将生成根的左子树（也为平衡二叉搜索树），中间元素右侧的元素将生成根的右子树（也为平衡二叉搜索树），由于左右元素总数之差不大于1，整个树此时为平衡二叉搜索树（若数组元素总数为奇数，"中间元素"左右侧元素数相同，若数组为偶数，"中间元素"左侧元素总数比右侧多一个）

若有序数组为空，函数直接返回。否则生成值为中间元素的根节点，分别生成中间元素左右侧的部分有序数组，以它们为参数，分别调用递归函数，得到的返回值作为根节点的左右子树，最后返回根节点。

#### 代码： ####

/**
     * 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) {
        
            if( nums.size()==0 )
                return NULL;
            int n=( nums.size() )/2;
            TreeNode* p=new TreeNode( nums[n] );
            vector<int> left,right;
            int i;
            for( i=0;i<n;i++ )
                left.push_back( nums[i] );
            for( i=n+1;i<nums.size();i++ )
                right.push_back( nums[i] );
            p->left=sortedArrayToBST( left );
            p->right=sortedArrayToBST( right );
            return p;   
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200506195052989.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70