【第四轮】6.28 - 7.4 Career Cup 4.3

4.3 Given a sorted (increasingorder) array with unique integer elements, write analgorithm to create a binary search tree with minimal height.

请参加活动的童鞋跟帖回复自己的解法，回复请参考以下格式：

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎探讨各种follow up questions，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改

【解题思路】
  Use binary search, divide and conquer, and recursion to create a balance tree，which has the min height.
【时间复杂度】
  each element is visited once, so time complexity is O(n)
【空间复杂度】
O(n) space for the tree, and O(log(n)) stack space for the recursion
【gist link】
https://gist.github.com/zhongyn/718996e13de82d5f44ff
class Node {
  int val;
  Node left = null;
  Node right = null;
  public Node(int v) {
    val = v;
  }
}

class Solution {
  public Node createBST(int[] a) {
    return subTree(a, 0, a.length - 1);
  }

  public Node subTree(int[] a, int start, int end) {
    if (start > end) {
      return null;
    }
    int m = (start + end) / 2;
    Node p = new Node(a[m]);
    p.left = subTree(a, start, m - 1);
    p.right = subTree(a, m + 1, end);
    return p;
  }
}

【解题思路】递归分治建树
【时间复杂度】每个节点访问一次所以是O(N)
【空间复杂度】
O(N)存储二叉树，递归空间O(logN)
【gist link】

https://gist.github.com/iFighting/742fab34d4f8d4d6bc0a

【解题思路】divide & conquer
【时间复杂度】O(n)
【空间复杂度】递归深度O(logn)消耗system stack + 结果O(n)
【gist link】
https://gist.github.com/zhangxin0804/23a3bf44ad4526102d3e

【解题思路】
递归构造二叉平衡树
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/alikewmk ... 8#file-4-3-bst-java

【解题思路】recursive in C++.
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】
gist.github.com/frozenfire888/9230ce43d9c76430c934