专栏首页Leetcode名企之路【Leetcode】108. 将有序数组转换为二叉搜索树

【Leetcode】108. 将有序数组转换为二叉搜索树

题目

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

      0
     / \
   -3   9
   /   /
 -10  5

题解

递归的去构造左子树和右子树就好了。 递归的时候带上左子树左右子树的边界就可以了。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null) {
            return null;
        }
        return helper(nums, 0, nums.length - 1);
    }

    public TreeNode helper(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        if (left == right) {
            return new TreeNode(nums[left]);
        }

        int mid = (left + right) / 2;
        TreeNode current = new TreeNode(nums[mid]);
        current.left = helper(nums, left, mid - 1);
        current.right = helper(nums, mid + 1, right);
        return current;
    }
}

本文分享自微信公众号 - Leetcode名企之路(DailyLeetCode)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-15

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Leetcode】53. 最大子序和

    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例:

    Leetcode名企之路
  • 【Leetcode】59. 螺旋矩阵 II

    给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

    Leetcode名企之路
  • 【Leetcode】59. 螺旋矩阵 II

    给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

    Leetcode名企之路
  • 2018年各大互联网前端面试题二(滴滴打车)

    王小婷
  • leetcode周赛(195)

    给你一个整数数组 arr 和一个整数 k ,其中数组长度是偶数,值为 n 。现在需要把数组恰好分成 n / 2 对,以使每对数字的和都能够被 k 整除。

    你的益达
  • 【LeetCode】45. Jump Game II

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • leetcode 26 Remove Duplicates from Sorted Array

    Remove Duplicates from Sorted ArrayTotal Accepted: 66627 Total Submissions: 2127...

    流川疯
  • [Leetcode][python]Permutations II/全排列 II

    详见上一题:http://blog.csdn.net/qqxx6661/article/details/78154064 投机取巧:将数组排序,然后就可以和...

    后端技术漫谈
  • 【LeetCode】215. 数组中的第K个最大元素

    在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

    韩旭051
  • LeetCode 565. 数组嵌套

    索引从0开始长度为N的数组A,包含0到N - 1的所有整数。 找到最大的集合S并返回其大小,其中 S[i] = {A[i], A[A[i]], A[A[A[i...

    Michael阿明

扫码关注云+社区

领取腾讯云代金券