C++怎么将有序数组转为二叉搜索树
本篇内容介绍了“C++怎么将有序数组转为二叉搜索树”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
创新互联坚持“要么做到,要么别承诺”的工作理念,服务领域包括:成都网站建设、网站建设、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的分宜网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!
将有序数组转为二叉搜索树
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& nums) { return helper(nums, 0 , (int)nums.size() - 1); } TreeNode* helper(vector & 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& nums) { if (nums.empty()) return NULL; int mid = nums.size() / 2; TreeNode *cur = new TreeNode(nums[mid]); vector left(nums.begin(), nums.begin() + mid), right(nums.begin() + mid + 1, nums.end()); cur->left = sortedArrayToBST(left); cur->right = sortedArrayToBST(right); return cur; } };
“C++怎么将有序数组转为二叉搜索树”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!
当前名称:C++怎么将有序数组转为二叉搜索树
分享地址:http://pwwzsj.com/article/isjchi.html