javascript - 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);
}           
       
       

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));
}

编辑:正如蓝天观察到的，childNodes 没有 .indexOf()。使用 Array.prototype.indexOf.call() 更新