DOM樹遍歷

我最近採訪了Facebook的一個前端工程師的職位。對於我的手機屏幕，我是以下問題：給定DOM樹中的節點，從相同的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); 
}

來源

2013-11-04 thedjpetersen

你沒有得到這份工作？ – alex

我沒有 - 面試過程中的口頭反饋很好，所以我想我必須錯過我的解決方案。 – thedjpetersen

您是否特意要求使用遞歸？迭代在這種情況下會簡單得多。另外，我們有關於DOM樹/結構/元素類型的_zero_信息？除了childNode數組中的索引位置之外，沒有可用的信息？ –

由於至少阿克塞爾顯示在迭代求解的興趣，在這裏它是：

給定兩個樹具有相同的結構，並且所述第一樹內的指定節點，找到在第二樹的節點在結構中具有相同的位置。

如果我們有大約兩棵樹然後每個節點的位置可被表徵爲從其中路徑中的每個步驟被指定爲索引到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更新（）

來源

2013-11-05 00:10:24

不錯，雖然我們正在審查代碼 - 在緩存path.length沒有意義，因爲它是一個數組而不是NodeList，所以訪問.length是O（1） –

兩年後，不應該使用'current。 parentNode.children'因爲'.children'只會返回HTML元素？看起來，對'childNodes'的調用包含[不僅僅是HTML元素]（http://stackoverflow.com/questions/16762027/difference-between-javascript-childnodes-children） – Morklympious

@Morklympious如果你用過那麼孩子們就不會有相同的結構，記住註釋是文檔結構的一部分。 –

我會遍歷平行的兩棵樹，當我在treeA到了節點返回並行節點。

來源

2014-07-07 15:52:02 kennytilton

你不覺得效率不高嗎？當你遍歷**到節點**時，你會遇到需要不必要檢查的分支，導致算法效率低下（假設你的節點在分支B中，而分支A中有1000個子孫）。相反，如果你從節點遍歷到根，這將是有效的。 –

相反的Array.prototype.indexOf.call，您可以使用Array.from（在ES6標準化）：

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

來源

2016-12-29 01:55:52 amilajack

這裏是平行穿越解決方案

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

它的時間複雜度爲O（N）和最差我們需要遍歷整個樹。

我不認爲它比先查找路徑解決方案效率較低。在每個級別都有一個對indexOf的調用，它可能需要遍歷該級別上的所有節點以查找索引。

來源

2018-01-19 13:14:57

回答

相關問題