Convert Sorted Array to Binary Search Tree -- LeetCode

原題リンク:  http://oj.leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
 
この問題は二分ルックアップツリーの問題で、秩序ある配列を二分ルックアップツリーに変換します.実は本質的に見ると、一つの配列を一つの木(つまり中点を根とし、左右を左右の子木とし、順次下りる)の配列と見なせば、一つの二分ルックアップ木に等価である.だからこの木を作るには、中間元素を根に変換し、左右のサブツリーを再帰的に構築することです.そこで我々はやはり二叉木再帰の方法で実現し,ルートを戻り値とし,各層再帰関数は中間要素をとり,現在のルートとして接点値を付与し,その後左右の接点に左右の区間の再帰関数戻り値を接続する.時間的複雑度はO(n)を木で遍歴するか,全体的な空間的複雑度はスタック空間O(logn)に結果を加えた空間O(n),余分な空間はO(logn),全体的にO(n)である.コードは次のとおりです. 

public TreeNode sortedArrayToBST(int[] num) {
    if(num==null || num.length==0)
        return null;
    return helper(num,0,num.length-1);
}
private TreeNode helper(int[] num, int l, int r)
{
    if(l>r)
        return null;
    int m = (l+r)/2;
    TreeNode root = new TreeNode(num[m]);
    root.left = helper(num,l,m-1);
    root.right = helper(num,m+1,r);
    return root;
}

これは良い問題で、模型は簡単ですが、遍歴と二分検索ツリーのデータ構造を考察して、比較的に電面の中で現れるのに適して、類似の問題はConvert Sorted List to Binary Search Treeがあります
ああ、この問題の非常に良い後続の問題で、異なるデータ構造、実現上も異なり、興味のある友达は見ることができます.