文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C++实现LeetCode(108.将有序数组转为二叉搜索树)

2024-04-02 19:55

关注

[LeetCode] 108.Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of everynode never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
/ \
-3   9
/   /
-10  5 

这道题是要将有序数组转为二叉搜索树,所谓二叉搜索树,是一种始终满足左<根<右的特性,如果将二叉搜索树按中序遍历的话,得到的就是一个有序数组了。那么反过来,我们可以得知,根节点应该是有序数组的中间点,从中间点分开为左右两个有序数组,在分别找出其中间点作为原中间点的左右两个子节点,这不就是是二分查找法的核心思想么。所以这道题考的就是二分查找法,代码如下:

解法一:


class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0 , (int)nums.size() - 1);
    }
    TreeNode* helper(vector<int>& nums, int left, int right) {
        if (left > right) return NULL;
        int mid = left + (right - left) / 2;
        TreeNode *cur = new TreeNode(nums[mid]);
        cur->left = helper(nums, left, mid - 1);
        cur->right = helper(nums, mid + 1, right);
        return cur;
    }
};

我们也可以不使用额外的递归函数,而是在原函数中完成递归,由于原函数的参数是一个数组,所以当把输入数组的中间数字取出来后,需要把所有两端的数组组成一个新的数组,并且分别调用递归函数,并且连到新创建的cur结点的左右子结点上面,参见代码如下:

解法二:


class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) return NULL;
        int mid = nums.size() / 2;
        TreeNode *cur = new TreeNode(nums[mid]);
        vector<int> left(nums.begin(), nums.begin() + mid), right(nums.begin() + mid + 1, nums.end());
        cur->left = sortedArrayToBST(left);
        cur->right = sortedArrayToBST(right);
        return cur;
    }
};

类似题目:

Convert Sorted List to Binary Search Tree

参考资料:

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/35220/My-Accepted-Java-Solution

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/35394/6-lines-Java-Accepted-Solution

到此这篇关于C++实现LeetCode(108.将有序数组转为二叉搜索树)的文章就介绍到这了,更多相关C++实现将有序数组转为二叉搜索树内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯