【Leetcode108】关关刷题日记65–Convert Sorted Array to Binary Search Tree- 专知

会员服务 ·

【Leetcode108】关关刷题日记65–Convert Sorted Array to Binary Search Tree

关关

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记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);
    }};