108. Convert Sorted Array to Binary Search Tree

发布时间：2020-12-14 04:38:02 所属栏目：大数据来源：网络整理

导读：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

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,5,9],One possible answer is: [0,9,-10,null,5],which represents the following height balanced BST:

      0
     /    -3   9
   /   /
 -10  5

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length == 0) return null;
        return help(nums,nums.length - 1);
    }
    public TreeNode help(int[] nums,int start,int end){
        int l = end - start;
        if(l < 0) return null;
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = help(nums,start,mid - 1);
        root.right = help(nums,mid+1,end);
        return root;
    }
}

没什么特殊的，每一步都是把中间的当作root，然后两边作为subtree。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!