30

私は最近、Facebook でフロントエンド エンジニアの職について面接を受けました。私の携帯電話の画面では、次の質問がありました。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);
}
4

4 に答える 4

23

少なくとも Axel は反復ソリューションに関心を示したので、以下に示します。

同じ構造を持つ 2 つのツリーと、最初のツリー内の指定されたノードが与えられた場合、構造内の同じ位置にある 2 番目のツリー内のノードを見つけます。

2 つのツリーに関する他の情報がない場合、各ノードの位置は、パスの各ステップが 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() による更新

于 2013-11-05T00:10:24.410 に答える
3

の代わりにArray.prototype.indexOf.call、以下を使用できますArray.from(ES6 で標準化):

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

于 2016-12-29T01:55:52.590 に答える
0

2 つのツリーを並行してトラバースし、treeA のノードに到達すると、並行ノードを返します。

于 2014-07-07T15:52:02.617 に答える