专栏首页SnailTyanConvert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

1. 问题描述

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

2. 求解

这个题主要是根据一个有序数组构造二叉查找树(树的左结点小于根节点,根节点小于右结点,子树具有同样的性质)。构造方法主要是递归,每次构建子树时都需要将数组分成左右两半,左边的构建左子树,右边的构建右子树,中间元素构造根节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildBinarySearchTree(nums, 0, nums.length - 1);
    }

    public TreeNode buildBinarySearchTree(int[] nums, int start, int end) {
        if(start > end) {
            return null;
        }
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildBinarySearchTree(nums, start, mid - 1);
        root.right = buildBinarySearchTree(nums, mid + 1, end);
        return root;
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 674. Longest Continuous Increasing Subsequence

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • Leetcode 75. Sort Colors

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • Leetcode 137. Single Number II

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 1. Two Sum(HashMap储存数组的值和索引)

    Given an array of integers, return indices of the two numbers such that they add...

    yesr
  • Leetcode 1444. 切披萨的方案数(DP,类似石材切割,二维前缀和)

    给你一个 rows x cols 大小的矩形披萨和一个整数 k ,矩形包含两种字符: 'A' (表示苹果)和 '.' (表示空白格子)。你需要切披萨 k-1 次...

    glm233
  • PHP二分查找

    这是属于查找类型的题目,因为数组是一个升序排列的整数叔组所以很容易想到使用二分查找这种思想来实现 O(log n) 级别的效率获取答案结果。代码如下

    大眼瞪小眼
  • LeetCode刷题DAY 8:两数之和

    给定一个整数数组 nums 和一个目标值 target,在该数组中找出和为目标值的那两个整数的数组下标。如nums = [2, 7, 11, 15], targ...

    三猫
  • 每日两题 T35

    ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

    合一大师
  • 创建SAS Format的几种方法

    不管是做AD还是TFL,我们经常会碰到要创建Format。当Format中条目不多时我们可以直接用PROC FORMAT来创建,但是当条目很多时,这种方法就不方...

    专业余码农
  • 兼容 - 纯代码完美适配 iPhoneX

    本文主要针对适配 iPhoneX列出一些关键点,仔细阅读可完美适配 iPhoneX,其中还有一些是适配 iOS11的, 话不多少,开始正餐。

    進无尽

扫码关注云+社区

领取腾讯云代金券