Leetcode——108. Convert Sorted Array to Binary Search Tree

程序员文章站 2022-07-15 12:42:27

...

题目原址

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/

题目描述

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

给定一个升序数组，要求按照数组的值构造处一个二叉搜索树BSF。

二叉搜索树：它或者是一棵空树，
或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。

AC代码

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
            return Bst(nums, 0, nums.length - 1);
    }
    public TreeNode Bst(int[] nums, int i, int j) {
        // TODO Auto-generated method stub
        if(i > j)
            return null;
        //数组中间的数作为根节点
        int medium = (i + j) / 2;
        TreeNode tn = new TreeNode(nums[medium]);
        //递归数组左边的数
        tn.left = Bst(nums, i, medium - 1);
        //递归数组右边的数  
        tn.right = Bst(nums, medium + 1, j);

        return tn;
    }

}