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

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

原文发布于微信公众号 - 专知(Quan_Zhuanzhi)

原文发表时间:2017-12-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

【Leetcode 206】关关的刷题日记70 – Leetcode 206. Reverse Linked List

关关的刷题日记70 – Leetcode 206. Reverse Linked List 题目 Reverse a singly linked list. 题...

34580
来自专栏专知

关关的刷题日记07——Leetcode 26. Remove Duplicates from Sorted Array 方法1

关小刷刷题07 – Leetcode 26. Remove Duplicates from Sorted Array 方法1 题目 Given a sorted...

30740
来自专栏专知

【Leetcode83】关关的刷题日记72– Remove Duplicates from Sorted List

关关的刷题日记72 – Leetcode 83. Remove Duplicates from Sorted List 题目 Given a sorted li...

28650
来自专栏专知

【关关的刷题日记57】Leetcode 101. Symmetric Tree

关关的刷题日记57 – Leetcode 101. Symmetric Tree 题目 ? 题目的意思是判断一棵树是否是镜像的,此处镜像指的是中心对称的树。 思...

31840
来自专栏专知

关关的刷题日记81 – Leetcode 258. Add Digits

关关的刷题日记81 – Leetcode 258. Add Digits 题目 Given a non-negative integer num, repeat...

28570
来自专栏专知

【 关关的刷题日记53】 Leetcode 100. Same Tree

关关的刷题日记53 – Leetcode 100. Same Tree 题目 Given two binary trees, write a function ...

33670
来自专栏专知

关关的刷题日记88 – Leetcode 367.Valid Perfect Square

关关的刷题日记88 – Leetcode 367.Valid Perfect Square 题目 Given a positive integer num, w...

31490
来自专栏专知

【LeetCode 242】 关关的刷题日记36 Valid Anagram

关关的刷题日记36 – Leetcode 242. Valid Anagram 题目 Given two strings s and t, write a fu...

36390
来自专栏专知

关关的刷题日记97 – Leetcode 105. Construct Binary Tree

关关的刷题日记97 – Leetcode 105. Construct Binary Tree 题目 Given preorder and inorder tr...

31140
来自专栏专知

关关的刷题日记79 – Leetcode 9 Palindrome Number

关关的刷题日记79 – Leetcode 9 Palindrome Number 题目 Determine whether an integer is a pa...

37580

扫码关注云+社区

领取腾讯云代金券