题目

给一个排序数组（从小到大），将其转换为一棵高度最小的排序二叉树。

样例
给出数组[1,2,3,4,5,6,7], 返回

sortTree.PNG

分析

显然这个问题可以用递归解决。
中间的节点总是在根节点，所以我们不停的找到中间节点即可，然后分别递归处理左子树和右子树即可

代码

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param A: an integer array
     * @return: a tree node
     */
    public TreeNode sortedArrayToBST(int[] A) {  
        // write your code here
        if(A == null) return null;  
        TreeNode root = null;  
        return newTreeNode (root, A, 0, A.length-1); 
    }
    
    public TreeNode newTreeNode (TreeNode node, int[] A, int start, int end) {  
        if (start > end) {return null; }  
        //node = new TreeNode(0);  
        int mid = end - (end - start)/2;  
        node.val = A[mid];  
        node.left = newTreeNode(node.left, A, start, mid - 1);  
        node.right = newTreeNode(node.right, A, mid + 1, end);  
        return node;  
    } 
}