把排序数组转换为高度最小的二叉搜索树

题目

给一个排序数组(从小到大),将其转换为一棵高度最小的排序二叉树。http://www.lintcode.com/zh-cn/problem/convert-sorted-array-to-binary-search-tree-with-minimal-height/

分析

要达到高度最小,二叉树需要尽可能的平衡,左子树的高度和右子树的高度趋于一致。以奇数个数的元素为例,假设总共有七个元素,那么当根元素的左子树包含3个元素,右子树包含3个元素,同时左右子树都是一颗高度为2的树,此时形成的二叉搜索树高度满足最低。

显然可以推断出,二叉树的根元素一定是数组中位置“居中”的元素。如果数组的个数是偶数个呢? [size/2] 和 [size/2 + 1 ]的元素都可以作为根元素。

为了简单起见,我们就直接取 索引为[size/2]的元素作为根元素。有了根元素之后,如何构建左右子树呢?当然是递归刚才的算法即可,代码呼之欲出了。

代码

public class Solution {
    
    TreeNode createTree(int[] A, int start, int end){
        
        
        int size = end - start + 1;
        
        if( size == 2){
            TreeNode node = new TreeNode(A[start]);
            node.right = new TreeNode(A[end]);
            return node;
        }else if( size == 1){
            return new TreeNode(A[start]);
        }else if(size >= 3){
            TreeNode node = new TreeNode(A[(start+end)/2]);
            node.left = createTree(A, start, (start+end)/2 - 1);
            node.right = createTree(A, (start+end)/2 + 1, end);
            return node;
        }else{
            return null;
        }
        
    }
    /*
     * @param A: an integer array
     * @return: A tree node
     */
    public TreeNode sortedArrayToBST(int[] A) {
        // write your code here
        return createTree(A, 0, A.length - 1);
    }
}
Show Comments

Get the latest posts delivered right to your inbox.