LeetCode 108. 将有序数组转换为二叉搜索树 | C++语言版

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

题目描述

题目地址：108. 将有序数组转换为二叉搜索树

解题思路

思路一：使用递归

代码实现

C++

/*** 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:TreeNode* traversal(vector<int>& nums,int left,int right){if(left>right) return NULL;int mid=left+((right-left)/2);TreeNode* root=new TreeNode(nums[mid]);//定义的区间为左闭右闭[left,mid-1]root->left=traversal(nums,left,mid-1);//定义的区间为左闭右闭[mid+1,right]root->right=traversal(nums,mid+1,right);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {//一个整数数组 nums(升序) 排列，将其转换为一棵高度平衡二叉搜索树(每个节点的左右两个子树的高度差的绝对值不超过1)//寻找数组中间位置的节点作为分割点，分割点作为当前节点，然后递归左区间和右区间//如果数组长度为偶数，中间节点有两个，取哪一个都可以，只不过构成了不同的平衡二叉搜索树//定义的区间为左闭右闭[0,nums.size()-1]TreeNode* root=traversal(nums,0,nums.size()-1);return root;}
};

运行结果

参考文章：

https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html#%E9%80%92%E5%BD%92

思路二：减少遍历节点数

代码实现

C++

在这里插入代码片

运行结果

参考文章：