算法-二叉树篇26-将有序数组转换为二叉搜索树

将有序数组转换为二叉搜索树

力扣题目链接

题目描述

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

解题思路

很简单的遇到递归题目，对数组取半，然后构建中间节点作为该数组对应的树，然后左右两边切割数组递归下去。

题解 class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { if(nums.size() == 0){ return nullptr; } if(nums.size() == 1){ TreeNode* temp = new TreeNode(nums[0]); return temp; } int n = nums.size() / 2; vector<int> arr1(nums.begin(), nums.begin() + n); vector<int> arr2(nums.begin() + n + 1, nums.end()); TreeNode* temp = new TreeNode(nums[n]); temp->left = sortedArrayToBST(arr1); temp->right = sortedArrayToBST(arr2); return temp; } };