177.Convert Sorted Array to Binary Search Tree With Minimal Height

1.Description(Easy)

Given a sorted (increasing order) array, Convert it to create a binary tree with minimal height.

Notice

There may exist multiple valid solutions, return any of them.

Example

Given[1,2,3,4,5,6,7], return

     4
   /   \
  2     6
 / \    / \
1   3  5   7

2.Code

解决方法是选中点构造根节点，然后递归的构造左子树和右子树。

If we build BST from array, we can build it from top to bottom, like

1. choose the middle one as root,

2. build left sub BST via left part array

3. build right sub BST via right part array

4. do this recursively.

public TreeNode sortedArrayToBST(int[] A) {  
        return dfs(A,0,A.length-1);
    } 


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