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

梦想不抛弃苦心追求的人,只要不停止追求,你们会沐浴在梦想的光辉之中。再美好的梦想与目标,再完美的计划和方案,如果不能尽快在行动中落实,最终只能是纸上谈兵,空想一番。只要瞄准了大方向,坚持不懈地做下去,才能够扫除挡在梦想前面的障碍,实现美好的人生蓝图。将有序数组转化为平衡的二叉搜索树,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

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

问题:

在这里插入图片描述

思路:

分治递归:

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

递归函数的功能为生成以有序数组中间元素为根的平衡二叉搜索树(参数为有序数组,返回根节点),则中间元素左侧的元素将生成根的左子树(也为平衡二叉搜索树),中间元素右侧的元素将生成根的右子树(也为平衡二叉搜索树),由于左右元素总数之差不大于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;   
    }
};

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/153859.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之家——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!