取两个HTML节点最近的公共父节点

gistfile1.js

function getCommonParent(el1,el2){

    var parents1 = [];
    var el = el1;
    while(el) {
        parents1.unshift(el);
        el = el.parentNode;
    }

    var parents2 = [];
    var el = el2;
    while(el) {
        parents2.unshift(el);
        el = el.parentNode;
    }

    var i = 0;

    while(i<parents1.length && i<parents2.length && parents1[i+1] == parents2[i+1])
        i++;

    return parents1[i];
}

如果是 detached 的 el, 那么会错误的返回 parents1[0], 但应当返回 null, 建议加一个检查 parents1[0]是否等于 parents2[0]

这样可行否

function getCommonParent(el1,el2){
    var parents1 = [];
    var el = el1;
    while(el) {
        parents1.unshift(el);
        el = el.parentNode;
    }

    var parents2 = [];
    var el = el2;
    while(el) {
        if(parents1.indexOf(el)>0){
            return el;
        }else
        {
            el = el.parentNode;
        }
    }
 return null;
}
···

@surgesoft 你这个是不行的，indexOf(el)这步应该是每次都要遍历整个数组，性能损失比winter的代码高多了。

@surgesoft 如果 parentNode 的速度比 indexOf 慢很多，那么就是可行的，我不太清楚这二者的速度差异

function getCommonParent (el1, el2) {
    var el = el1.parentNode
    while (el) {
        if (el.contains(el2)) return el
        el = el.parentNode
    }
}

本来我也不知道contains()的效率，简单bench了一下比winter的方法快很多。

@yyx990803
contains应该是正解

var isCommon = function(nodea,nodeb,deepDelta) {
    while(deepDelta--) {
        nodea = nodea.parentNode;
    }
    while(nodea != nodeb) {
        nodea = nodea.parentNode;
        nodeb = nodeb.parentNode;
    }
    return nodea;
}

var findParent = function(a,b) {
    var _a = a;
    var aDeep = 0;
    while(_a) {
        _a = _a.parentNode;
        aDeep++;
    }

    var _b = b;
    var bDeep = 0;
    while(_b) {
        _b = _b.parentNode;
        bDeep++;
    }
    var deepDelta;
    if( aDeep > bDeep ) {
        deepDelta = aDeep - bDeep;
        return isCommon(a,b,deepDelta);
    } else {
        deepDelta = bDeep - aDeep;
        return isCommon(b,a,deepDelta);
    }

};

随便玩玩。。

@yyx990803 很明显计子是故意这么写的，估计随便写一个bench一下都比lz的快，contains的效率不见得最优，嘿嘿

function getCommonParent(el1, el2) {
    var flag = +new Date;

    while (el1) {
        el1['data-flag'] = flag;
        el1 = el1.parentNode;
    }

    while (el2) {
        if (el2['data-flag'] == flag) {
            return el2;
        }
        el2 = el2.parentNode;
    }
}

var rnative = /^[^{]+\{\s*\[native code/;

function isNative(fn) {
  return rnative.test(fn + "");
}

var contains = isNative(document.documentElement.contains) || document.documentElement.compareDocumentPosition ?
function(a, b) {
  var adown = a.nodeType === 9 ? a.documentElement : a,
      bup = b && b.parentNode;
  return a === bup || !! (bup && bup.nodeType === 1 && (
  adown.contains ? adown.contains(bup) : a.compareDocumentPosition && a.compareDocumentPosition(bup) & 16));
} : function(a, b) {
  if (b) {
    while ((b = b.parentNode)) {
      if (b === a) {
        return true;
      }
    }
  }
  return false;
};

function getCommonParentNew(el1, el2) {
  var parent;
  do {
    parent = el1.parentNode;
    if (contains(parent, el2)) {
      return parent;
    }
  }
  while (parent);

  return null;
}

http://jsperf.com/get-common-parent

function getCommonParent(el1, el2){

  if (el1 == el2) { 
    return el1.parentNode; 
  }

  function getParents(el){
    var parents = [];
    while(el) {
      parents.unshift(el);
      el = el.parentNode;
    }
    return parents;
  }

  var parents1 = getParents(el1);
  var parents2 = getParents(el2);

  var i = 0;
  var lenght = parents1.length > parents2.length ? parents1.length : parents2.length;

  while(i < length && parents1[i+1] == parents2[i+1]){
    i++;
  }

  return parents1[i];
}

暂时想到这么多

@hushicai 没有啦，我确实写得挺随便但是也确实没想到更好的办法啊

yyx990803的答案利用contains虽然不太清楚算法上的时间评估不过应该算工程上的最佳实践了吧

@tuliang 其实你的代码跟我算法一样啊 不过抽取个公共函数确实dry比较好，顺便length拼错了哦~

@lidaobing 道哥威武，因为被应用场景蒙蔽了双眼我确实没想到这一节

标准浏览器下，可以用Range来实现：

function getCommonParent(el1,el2) {
    if(document.createRange) {
        var range = document.createRange();
        range.setStart(el1,0);
        range.setEnd(el2,0);
        var rangeAncestor = range.commonAncestorContainer;
        return rangeAncestor;
    } else {
        //for ie...
    }
}

// Compare Position - MIT Licensed, John Resig
function comparePosition(a, b) {
    return a.compareDocumentPosition ?
            a.compareDocumentPosition(b) :
            a.contains ? ( a != b && a.contains(b) && 16 ) +
                    ( a != b && b.contains(a) && 8 ) +
                    ( a.sourceIndex >= 0 && b.sourceIndex >= 0 ?
                            (a.sourceIndex < b.sourceIndex && 4 ) + (a.sourceIndex > b.sourceIndex && 2 ) : 1 ) : 0;
}

function getCommonParent(el1, el2) {
    if (el1 == el2 || (comparePosition(el1, el2) & 0x10) === 0x10) {
        return el1;
    } else {
        return getCommonParent(el1.parentNode, el2);
    }
}

@wintercn 不应该使用unshift方法，应该使用push方法，相应的后面也就要从尾部开始了

@coffeesherk 实现很好，空间复杂度明显要小，++运算应该很快哦，做一点无关痛痒的修改

var _a = a.parentNode;
var aDeep = 0;
while(_a) {        // 这里少了一次 . 取值
    _a = _a.parentNode;
    aDeep++;
}

function getCommonParent(el1,el2) {
    if (!el1 || !el2)
        return null;

    var commonParent = null;
    var nodes = [el1, el2];
    for (var i=0; i<nodes.length; ++i) {
        var node = nodes[i];
        if (node.gcpVisited) {
            commonParent = node;
            break;
        }
        node.gcpVisited = true;
        if (node = node.parentNode) {
            nodes.push(node);
        }
    }

    while (node = nodes.pop()) {
        delete node.gcpVisited;
    }
    return commonParent;
}

两边一起来，如果离共同父类距离相近时则查询次数较少，但有设flag和清flag消耗，综合实力就不清楚了。

我也来一段吧

function getCommonParent(a,b){
    if(a.sourceIndex){ //for IE
        var sib = b.sourceIndex, sia = a.sourceIndex;
        if(sib < sia){
            return getCommonParent(b,a);
        }
        while((sib > sia) && (b = b.parentNode)){
            sib = b.sourceIndex;
        }
        return b && b.contains(a) ? b : null;
    }else{ //Not IE
        //...参考chaoren1641
    }
}

@cuixiping 真是各种高人啊...... 长见识了

再来一段使用的标准compareDocumentPosition的，把代码修改得简洁了一点。

function getCommonParent(a,b){
    var c = a.compareDocumentPosition(b);
    if(c & 8){
        return b.parentNode;
    }else if(c & 16){
        return a.parentNode;
    }else if(c & 6){
        while(!(8 & a.compareDocumentPosition(b=b.parentNode)));
        return b;
    }
    return null;
}