nodos - manipular elementos html javascript

Recorrido del árbol DOM

Question

Recientemente me entrevisté para un puesto de ingeniero de frontend en Facebook. Para la pantalla de mi teléfono, era la siguiente pregunta: Dado un nodo de un árbol DOM, busque el nodo en la misma posición de un árbol DOM idéntico. Vea el diagrama a continuación para mayor claridad.

 A         B

 O        O
 |/       |/
 O O      O O
  /|/      /|/
 O O O    O O O
      /        /
       O        O

Aquí estaba mi solución, me preguntaba qué podría haber hecho para mejorarla / optimizarla.

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

Aquí hay una solución de desplazamiento paralelo.

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

    var nodeB = null;

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

    return nodeB;
}

La complejidad del tiempo es O (N) y, en el peor de los casos, necesitamos atravesar todo el árbol.

No creo que sea menos eficiente que la solución al encontrar el camino primero. En cada nivel hay una llamada a indexOf que puede necesitar atravesar todos los nodos en ese nivel para encontrar el índice.

Answer 2

Atravesaría los dos árboles en paralelo y cuando llegara al nodo en el árbol, devolvería el nodo paralelo.

Answer 3

Como al menos Axel mostró interés en una solución iterativa, aquí está:

Dados dos árboles que tienen una estructura idéntica y un nodo específico dentro del primer árbol, ubique el nodo en el segundo árbol con la misma posición dentro de la estructura.

Si no tenemos otra información sobre los dos árboles, la posición de cada nodo se puede caracterizar como una ruta desde el nodo raíz, donde cada paso en la ruta se especifica como un índice en la matriz 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));
}

EDITAR: Como se observó en Blue Skies, childNodes no tiene .indexOf (). Actualizando con Array.prototype.indexOf.call ()

Answer 4

En lugar de Array.prototype.indexOf.call , puede usar Array.from (estandarizado en ES6):

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