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

題目

把一個有序數(shù)組轉(zhuǎn)換成二叉樹，要求左右深度不能大于一。

思路

有這個深度要求，我們就只能從中間一分為二，對于左右子樹，也同樣一分為二，所以就是遞歸去做。

代碼

 public TreeNode sortedArrayToBST(int[] nums) {
         if (nums==null) {
            return null;
        }
         
        return convertTree(nums,0,nums.length-1);//遞歸函數(shù)
        }


    private TreeNode convertTree(int[] nums, int l, int r) {
        if (l<=r) {
            int mid =(l+r)/2;
            TreeNode root=new TreeNode(nums[mid]);//取中間的值為根節(jié)點
            root.left=convertTree(nums, l, mid-1);//遞歸獲得左右子樹
            root.right=convertTree(nums, mid+1, r);
            return root;
        }else {
            return null;
        }
    }