电商网站开发制作,中石油企业邮箱怎么注册,菏泽网站建设便宜臻动传媒,网站建设需求书#x1f604;#x1f60a;#x1f606;#x1f603;#x1f604;#x1f60a;#x1f606;#x1f603;
开始cpp刷题之旅。
依旧是追求耗时0s的一天。 108. 将有序数组转换为二叉搜索树
给你一个整数数组 nums #xff0c;其中元素已经按 升序 排列#xff0c;请你…
开始cpp刷题之旅。
依旧是追求耗时0s的一天。 108. 将有序数组转换为二叉搜索树
给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1
输入nums [-10,-3,0,5,9] 输出[0,-3,9,-10,null,5] 解释[0,-10,5,null,-3,null,9] 也将被视为正确答案
示例 2
输入nums [1,3] 输出[3,1] 解释[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
解题
注意给的数组是升序的。
二叉搜索树若它的左子树不空则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空则右子树上所有结点的值均大于它的根结点的值 它的左、右子树也分别为二叉排序树。
所以这里的根节点我们应该去数组的中间值
然后将小于该值的放在左子树上大于该值的放在右子树上。
使用递归去完成
class Solution {
public:TreeNode* sortedArrayToBST(vectorint nums) {return bst(nums,0,nums.size()-1);}TreeNode* bst(vectorint nums, int l, int r){if(lr) return nullptr; //如果lr返回nullint mid lr1; //取l和r的中间值TreeNode* res new TreeNode(nums[mid]); //创建新的树将中间值作为根节点res-left bst(nums,l,mid-1); //小于该值的放在左子树上res-right bst(nums,mid1,r); //大于该值的放在右子树上return res;}
};
