刚看了geekforgeek烙印代码果然一坨屎逻辑混乱 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

刚看了geekforgeek烙印代码果然一坨屎逻辑混乱

刚看了geekforgeek烙印代码果然一坨屎逻辑混乱# JobHunting - 待字闺中

H*52017-09-22 07:09

1 楼

lowest common ancestor with parent.
看了这行:
if(ancestor.containsKey(q)!=ancestor.isEmpty())
我第一遍是觉得晕的

H*52017-09-22 07:09

2 楼

whole code:
package Interview.PhoneInterview.LinkedIn.Tree.BTree.Recurse.
LowestCommonAncestor;
import java.util.HashMap;
import java.util.Map;
class BTreeNodeWithParent{

int val;
BTreeNodeWithParent left;
BTreeNodeWithParent right;
BTreeNodeWithParent parent;
BTreeNodeWithParent(int val){
this.val=val;
this.left=this.right=this.parent=null;
}
}
public class LowestCommonAncestorOfABinaryTreeWithParent {
BTreeNodeWithParent LCA(BTreeNodeWithParent p, BTreeNodeWithParent q)
{
// Creata a map to store ancestors of n1
Map ancestors = new HashMap<
BTreeNodeWithParent, Boolean>();

// Insert n1 and all its ancestors in map
while (p != null)
{
ancestors.put(q, Boolean.TRUE);
p = p.parent;
}

// Check if n2 or any of its ancestors is in
// map.
while (q != null)
{
if (ancestors.containsKey(q) != ancestors.isEmpty())
return q;
q = q.parent;
}
return null;
}
}