DOM树遍历

Question

最近我参加了前端工程师职位的面试。在电话面试中，我被问到以下问题：给定DOM树中的一个节点，找到相同位置上的节点以及对应的一个相同的DOM树。请参考下面的图示，以便更好地理解。

 A         B

 O        O
 |\       |\
 O O      O O
  /|\      /|\
 O O O    O O O
      \        \
       O        O

这是我的解决方案，我想知道我能做些什么来改进/优化它。

var rootA, rootB;

function findNodeB(nodeA) {
    // Variable to store path up the DOM tree
    var travelPath = [];
    
    // Method to travel up the DOM tree and store path to exact node
    var establishPath = function(travelNode) {
        // If we have reached the top level node we want to return
        // otherwise we travel up another level on the tree
        if (travelNode === rootA) {
            return;
        } else {
            establishPath(travelNode.parentNode);
        }
        
        // We store the index of current child in our path
        var index = travelNode.parentNode.childNodes.indexOf(travelNode);
        travelPath.push(index);     
    }
    
    var traverseTree = function(bTreeNode, path) {
        if(path.length === 0) {
            return bTreeNode;
        } else {
            traverseTree(bTreeNode.childNodes[path.pop()], path);
        }
    }
    
    establishPath(rootB, nodeA);
    
    return traverseTree(rootB, travelPath);
}           
       
       

- thedjpetersen

---

你没有得到这份工作？ - alex

@Mike - 我很想看到一种迭代方法来处理这个问题，以便比较效率差异（并且为了学习目的）。 - Axel

好的，由于.childNodes集合没有indexOf()方法，我猜想这会对你造成很大的不利影响。 - Blue Skies

有趣的笔记，这也让我困惑了。然而，在真实情境中，“如果面试官是纳粹，那么‘对你非常不利’”，你会很快发现并通过Array.prototype.indexOf.call()进行解决。 - Mike Edwards

另外，只是挑剔一下 - establishPath的签名只需要一个参数，但你传递了两个参数，并且traverseTree在进行递归调用时需要返回自身（现在它只是进行了递归调用，但没有返回任何内容）。 - dchang

Answer 1

由于至少 Axel 对迭代解决方案表现出了兴趣，因此在这里给出：

给定两棵具有相同结构的树和第一棵树中指定的节点，在第二棵树中找到具有相同位置的节点。

如果我们没有关于这两棵树的其他信息，则每个节点的位置可以被描述为从根节点开始的路径，其中路径中的每一步都被指定为 childNode 数组中的索引。

function indexOf(arrLike, target) {
    return Array.prototype.indexOf.call(arrLike, target);
}

// Given a node and a tree, extract the nodes path 
function getPath(root, target) {
    var current = target;
    var path = [];
    while(current !== root) {
        path.unshift(indexOf(current.parentNode.childNodes, current));
        current = current.parentNode;
    }
    return path;
}

// Given a tree and a path, let's locate a node
function locateNodeFromPath(root, path) {
    var current = root;
    for(var i = 0, len = path.length; i < len; i++) {
        current = current.childNodes[path[i]];
    }
    return current;
}

function getDoppleganger(rootA, rootB, target) {
    return locateNodeFromPath(rootB, getPath(rootA, target));
}

编辑： 正如Blue Skies所指出的，childNodes没有.indexOf()方法。更新为Array.prototype.indexOf.call()

- Mike Edwards

---

很好，在我们进行代码审查时 - 缓存path.length没有意义，因为它是一个数组而不是NodeList，所以访问.length是O(1)。 - Benjamin Gruenbaum

两年后，这里应该使用 current.parentNode.children，因为 .children 只会返回 HTML 元素。看起来调用 childNodes 包含的不仅仅是 HTML 元素。 - Morklympious

@Morklympious 不完全是这样，因为如果你使用了 children，那么结构就不同了，记住注释是文档结构的一部分。 - user1971598

Answer 2

这里是并行遍历的解决方案。

function findDomNodeInTree(rootA, rootB, targetNode) {
    if (rootA === targetNode){
        return rootB;
    }

    let nodeB = null;

    for (let i=0; i<rootA.childNodes.length && nodeB === null; i++){
        nodeB = findDomNodeInTree(rootA.childNodes[i], rootB.childNodes[i], targetNode);
    }

    return nodeB;
}

这个算法的时间复杂度是O（N），在最坏情况下我们需要遍历整棵树。

我认为它不比先查找路径的解决方案低效。在每个层级上，都会调用indexOf函数，该函数可能需要遍历该层上的所有节点以查找索引。

- Yuriy Kvartsyanyy

---

可以请另一个人确认一下这个解决方案是否正确吗？我没有发现任何问题。 - Ekaitz Hernandez Troyas

Answer 3

可以使用 ES6 中标准化的 Array.from，而不是 Array.prototype.indexOf.call：

Array.from(travelNode.parentNode.childNodes).indexOf(travelNode);

- amilajack

---

好主意。唯一的取舍是prototype.index.call直接在对象上操作，而.from().indexOf()会创建一个浅拷贝，这将增加空间复杂度。这是一个容易在面试中解释清楚的权衡。 - Robby_rob

Answer 4

我会并行遍历这两棵树，当我到达treeA中的节点时，返回相应的并行节点。

- kennytilton

---

你不认为这很低效吗？当你遍历到某个节点时，你会遇到那些你不必要检查的分支，从而使算法变得低效（想象一下，如果你的节点在B分支上，而A分支有成千上万的子孙）。相反，如果你从节点向根遍历，这将更加高效。 - Om Shankar