网站建设免费,大连网站建设具体流程是什么,做透水砖的网站,禅城网站建设多少钱Problem: 108. 将有序数组转换为二叉搜索树 文章目录 题目描述思路复杂度Code 题目描述 思路
根据二叉搜索树中序遍历为一个有序序列的特点得到#xff1a; 1.定义左右下标left#xff0c;right分别指向有序序列的头尾#xff1b; 2.每次取出left和right的中间节点mid… Problem: 108. 将有序数组转换为二叉搜索树 文章目录 题目描述思路复杂度Code 题目描述 思路
根据二叉搜索树中序遍历为一个有序序列的特点得到 1.定义左右下标leftright分别指向有序序列的头尾 2.每次取出left和right的中间节点mid构造出根节点 3.递归得到根节点的左子树的区间范围是(left, mid - 1)递归退出条件为left right 4.递归得到根节点的右子树的区间范围是(mid 1, right) 复杂度
时间复杂度: O ( n ) O(n) O(n);其中 n n n为数组的长度树的节点个数 空间复杂度: O ( l o g n ) O(logn) O(logn) Code
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:/*** Converts an ordered array to a binary search tree** param nums Given array* return TreeNode**/TreeNode* sortedArrayToBST(vectorint nums) {return buildBST(nums, 0, nums.size() - 1);}private:/**** param nums Given array* param left The left root* param right The right root* return TreeNode**/TreeNode* buildBST(vectorint nums, int left, int right) {if (left right) {return nullptr;}int mid left (right - left) / 2;TreeNode* node new TreeNode(nums[mid]);node-left buildBST(nums, left, mid - 1);node-right buildBST(nums, mid 1, right);return node;}
};
