美文网首页
Convert Sorted Array to Binary S

Convert Sorted Array to Binary S

作者: BLUE_fdf9 | 来源:发表于2018-10-07 09:19 被阅读0次

题目
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:

  0
 / \

-3 9
/ /
-10 5

答案

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }
    
    public TreeNode helper(int[] nums, int left, int right) {
        if(left > right) return null;
        
        int m = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[m]);
        root.left = helper(nums, left, m - 1);
        root.right = helper(nums, m + 1, right);
        return root;
    }
}

相关文章

网友评论

      本文标题:Convert Sorted Array to Binary S

      本文链接:https://www.haomeiwen.com/subject/wkokaftx.html