邓英超 发表于 2013-7-30 15:42:11

[google面试题]Design 
an
 algorithm 
to
 find a
 path
 from
 one
 node 
in
 a
 binary
 tree
 to 
another

亮 发表于 2013-7-30 16:11:46

Good Answer: There will always be exactly one path: from the starting node to thelowest common ancestor of the nodes to these condnode.The goalist o identify thelowest common ancestor.For each node,keep track of a set of nodes in the binary tree(using a hashtable or a BST)as well as a current node.At each iteration,for each of the two current nodes,change the current node to be its parent and add it to the appropriate set.The first element that is added to one set when it is already present in the other set is the lowest common ancestor. This algorithm takes O(n) time,where n is the length of the path.For example,if we were finding the lowest common ancestor of 3and 15 in the above tree,our algorithm wouldo the following:Current node 1 | Current node 2 | Set 1 |Set 2-------------------------------------------------------- 3 |15 | 3 | 15 6 |12 | 3, 6 | 15, 12 17 |6 | 3, 6, 17 | 15, 12, 6To improve the solution,we actually only need to use one set instead of two.
页: [1]
查看完整版本: [google面试题]Design 
an
 algorithm 
to
 find a
 path
 from
 one
 node 
in
 a
 binary
 tree
 to 
another