关关的刷题日记65 – Leetcode 108. Convert Sorted Array to Binary Search Tree

题目

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

题目的意思是给定一个排好序的数组，要求将它转化成一个平衡二叉排序树。

思路

思路：每次选取该数组的中间值作为根节点，中间值左边的数构成左子树，右边的数构成右子树。左右子树的构造方法和这棵树的构造方法一样，采取递归的思路，递归函数可以设置两个整型参数用来表示左右边界。

class Solution {
public:
    TreeNode* dfs(int l, int r, vector<int>& nums)
    {
        if(l<=r)
        {
            TreeNode* root;
            root=new TreeNode(nums[(l+r)/2]);
            root->left=dfs(l, (l+r)/2-1 ,nums);
            root->right=dfs((l+r)/2+1, r, nums);
            return root; 
        }
        else
            return nullptr;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
       return dfs(0, nums.size()-1, nums);
    }
};

照顾好自己的身体，控制好自己的情绪，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。