[第二轮] 3/18-3/24 CareerCup 4.7

Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.

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

https://gist.github.com/ThunderXu/5187118
if a node has node1 in its left sub-tree and node2 in its right sub-tree, then it is the first common ancestor of node1 and node2

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

对自己的智力彻底丧失信心了。。。难道自己不是码农的材料

Because of avoid storing additional nodes, so just DFS。。。？Otherwise, online or offline algorithm could be used...

规格严格理性帝 发表于 2013-3-19 01:17
https://github.com/1094401996/CareerCup/blob/master/Chapter4/src/fourdot7/CommonAncestor.java

对自 ...

原来Java这么简单。。。

EchoMemory 发表于 2013-3-19 02:07
原来Java这么简单。。。

求别黑了。。。

规格严格理性帝 发表于 2013-3-19 21:08
求别黑了。。。

这哪是黑。。。模板写的很赞，学习了~

EchoMemory 发表于 2013-3-19 08:29
这哪是黑。。。模板写的很赞，学习了~

要是我自己写出来的就好了。。。。。。。书上的思路。。。。

first recursively find path from root to two nodes..用string表示path，往左为0，往右为1，Find the longest common sequence of two path strings
https://gist.github.com/chrislukkk/5202125
BST的话会方便很多..preorder traverse and found the first node that has value between that of two nodes(assume nodes exists in tree).

https://gist.github.com/5252636.git
recursively find the two nodes from the root's left and right