[第二轮] 3/11-3/17 CareerCup 4.3

Given a sorted (increasing order) array, write an algorithmto create a binary search tree with minimal height.

发帖规范:http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

Divide and conquer. In pseudo code :
buildtree:
if(array length is positive) {
add the middle node of the array to the tree;
buildtree from the array left to the middle point;
buildtree from the array right to the middle point;
}

In constructor(int[]) and buildTree()
https://gist.github.com/Zuohr/5128929

Node* build(ll,rr)
{
if check(ll,rr) return null;
int m=(ll+rr)/2;
node * a = new node(array[m]);
a->left=build(ll,m-1);
a->right=build(m+1,rr);
return a;
}
Node *root=build(...)

I choose the the middle value as the root and recur

my gist:https://gist.github.com/sing1ee/5135093

Recursively divide array by two to find the root of each sub trees.
https://github.com/moophis/careercup/blob/master/4.3.cpp

递归建立sub-tree，keep choosing middle value as the root in sub-tree
https://gist.github.com/chrislukkk/5174280

*递归的认识还是不到位，对这种思维还不习惯，希望通过大量做题能够解决这个问题
*通过递归每次取中间的那个，形式上和快排有点类似。。。。

https://github.com/1094401996/Ca ... /MinHeightTree.java

https://gist.github.com/ThunderXu/5175566
use recursion, take the middle element to be the root and recursively generate left sub-tree using left side of array and generate right sub-tree using right side of array.

recursively find the middle value of the array, and put the value as the root of the subtree

c++ implementation- function 4_3

https://github.com/StanleyLee/CareerCup/blob/master/4_1.cpp

规格严格理性帝 发表于 2013-3-16 10:17
*递归的认识还是不到位，对这种思维还不习惯，希望通过大量做题能够解决这个问题
*通过递归每次取中间的那 ...

是要发这个吧。https://github.com/1094401996/Ca ... ree/BinaryTree.java