将升序数组转化为bst

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

http://www.nowcoder.com/questionTerminal/7e5b00f94b254da599a9472fe5ab283d

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     *
     * @param num int整型vector
     * @return TreeNode类
     */
    TreeNode* sortedArrayToBST(vector<int>& num) {
        // write code here
        if (num.size() == 0) {
            return nullptr;
        }
        return createBST(num, 0, num.size() - 1);
    }

    TreeNode* createBST(vector<int>& num, int left, int right) {

        if (left > right) {
            return nullptr;
        }
        // left + (right - left) / 2和left + (right - left + 1) / 2 区别在于是左子树深些还
        // 是右子树深些
        int mid = left + (right - left + 1) / 2;
        TreeNode* root = new TreeNode(num[mid]);
        root->left = createBST(num, left, mid - 1);
        root->right = createBST(num, mid + 1, right);

        return root;
    }
};
全部评论

相关推荐

02-26 18:25
已编辑
南京大学 算法工程师
点赞 评论 收藏
分享
浪子陪都:简历最优秀的地方放到了后面,国奖,校级奖学金这些是最亮眼的。说明你跟同级别的学生不一样。 建议台灯这个,PCB布局布线这个词汇不专业,业内是PCB Layout,第二,单片机的板子一般不用考虑SI,PI 都是低速信号,只要遵循3W原则就好了。 单片机的项目太low了,技能这块,你要看一下BOSS直聘的招聘要求,按照别人的要求写,一些关键词可以增加你简历被检索到的概率。 主修课程不用写,这个没有人去关注的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务