BFE.devAI解答 - JavaScript 代码题
19. 相同结构的DOM tree上面寻找对应的节点

解法1：递归

可以通过深度优先搜索的方式，在两棵树中同时遍历，一旦找到与给定节点相同的节点，就返回该节点。具体流程如下：

• 若当前节点为空，则返回空。
• 若当前节点与给定节点相同，则返回对应节点。
• 否则递归遍历左子树和右子树，直到找到对应节点或两棵树遍历完毕。

时间复杂度为O(n)，空间复杂度为O(h)，其中n为节点总数，h为树的最大高度。

代码实现：

function findCorrespondingNode(rootA, rootB, nodeA) { if (!rootA || !rootB) return null; // 任意一棵树为空，说明没找到，返回空 if (rootA === nodeA) return rootB; // 找到对应节点，返回对应节点 // 递归遍历左子树和右子树，继续寻找 return findCorrespondingNode(rootA.left, rootB.left, nodeA) || findCorrespondingNode(rootA.right, rootB.right, nodeA) }

解法2：迭代

利用类似链表搜索的迭代方法，使用栈结构记录节点遍历顺序。从根节点开始遍历，一旦找到与给定节点相同的节点，就返回该节点。具体流程如下：

• 若栈为空则结束遍历。
• 弹出栈顶节点，检查该节点是否为给定节点。若是，则返回对应节点；否则将该节点的子节点依次压入栈中。
• 重复步骤1-2，直到找到对应节点或遍历完所有节点。

时间复杂度为O(n)，空间复杂度为O(n)，其中n为节点总数。

代码实现：

function findCorrespondingNode(rootA, rootB, nodeA) { const stackA = [], stackB = []; stackA.push(rootA); stackB.push(rootB); // 初始化栈

while (stackA.length) { const currA = stackA.pop(), currB = stackB.pop(); if (currA === nodeA) return currB; // 找到对应节点，返回对应节点 if (currA.right) { // 右子树先入栈，保证遍历顺序正确 stackA.push(currA.right); stackB.push(currB.right); } if (currA.left) { stackA.push(currA.left); stackB.push(currB.left); }
}

return null; // 遍历完整棵树都没找到对应节点，返回空 }

解法3：利用id规律

由于DOM Tree中每个节点都有一个id属性，可以通过在两棵树上同时递归查找节点id的方式，找到对应节点。具体流程如下：

• 若当前节点为空，则返回空。
• 检查当前节点的id与给定节点id是否相同。若是，则返回对应节点。
• 递归遍历当前节点的子节点，直到找到对应节点或遍历完所有节点。

时间复杂度为O(n)，空间复杂度为O(h)，其中n为节点总数，h为树的最大高度。

代码实现：

function findCorrespondingNode(rootA, rootB, nodeA) { if (!rootA || !rootB) return null; // 任意一棵树为空，说明没找到，返回空 if (rootA.id === nodeA.id) return rootB; // 找到对应节点，返回对应节点 for (let i = 0; i < rootA.children.length; i++) { const result = findCorrespondingNode(rootA.children[i], rootB.children[i], nodeA); if (result) return result; // 当前子树找到对应节点，直接返回 } return null; // 所有子树都遍历完了，没找到对应节点，返回空 }