淘宝面试题：有一个一亿节点的树，现下已知两个点，找这两个点的共同的祖先

淘宝面试题：有一个一亿节点的树，现在已知两个点，找这两个点的共同的祖先。
淘宝面试题：有一个一亿节点的树，现在已知两个点，找这两个点的共同的祖先。
这个题怎么做呢？
------解决方案--------------------
淘宝你好，淘宝再见……
------解决方案--------------------
树结构的，可以考虑每个节点不仅记录父节点，还要额外记录一下当前层次。
两个节点先比较下层次，让层次大的先找父节点，直到层次相同了。
两个节点再同时找父节点，并比较。
------解决方案--------------------
这不是一道题目，是一个观察你思维的一个case，你可以任意设计这个树结构，然后再根据你的思路继续问。
单单这一个题目，已知条件太少，我假设，不计较空间大小，树叶记录了所有自己的祖先节点，那不就太容易找了。
碰到这种，随机应变。
------解决方案--------------------
先把一个节点的所有父节点加到HASHSET里去，再在HASHSET里挨个找第二个节点的父。啥是找到了就是了。
------解决方案--------------------
第一个根节点肯定是他们共有的祖先，
如果找最近的公共祖先可参考 这篇文章：http://blog.****.net/v_july_v/article/details/18312089
------解决方案--------------------

引用:

第一个根节点肯定是他们共有的祖先，
如果找最近的公共祖先可参考 这篇文章：http://blog.****.net/v_july_v/article/details/18312089

说的也是，题目并没有说最近的祖先，也没有说找出所有的共同祖先，咱就说根节点就好了。