Задача: обход DOM-дерева
На этой странице
Задачи на обход DOM проверяют умение работать с деревом: написать свой getElementsByClassName (обход в глубину по children), найти ближайшего общего предка двух узлов, найти соответствующий узел в копии дерева (по пути индексов), посчитать глубину или собрать все текстовые узлы. Все они решаются DFS/BFS по дереву — рекурсией или стеком — и не требуют знания редких API.
Вопрос
Реализуйте getElementsByClassName(root, className) без встроенных методов поиска, функцию поиска ближайшего общего предка двух элементов и функцию, которая находит в клоне дерева узел, соответствующий узлу из оригинала.
getElementsByClassName
function getElementsByClassName(root, className) {
const result = [];
function walk(element) {
for (const child of element.children) { // только элементы, без текстовых узлов
if (child.classList.contains(className)) result.push(child);
walk(child);
}
}
walk(root);
return result;
}Итеративный вариант (без риска переполнения стека):
function getElementsByClassNameIterative(root, className) {
const result = [];
const stack = [...root.children].reverse();
while (stack.length) {
const el = stack.pop();
if (el.classList.contains(className)) result.push(el);
stack.push(...[...el.children].reverse()); // reverse сохраняет порядок документа
}
return result;
}Вариант с несколькими классами ("btn primary") — проверять каждый класс через every.
Ближайший общий предок
function commonAncestor(a, b) {
const ancestors = new Set();
for (let node = a; node; node = node.parentElement) ancestors.add(node);
for (let node = b; node; node = node.parentElement) {
if (ancestors.has(node)) return node;
}
return null;
}O(глубина). Если один узел — предок другого, вернется он сам. Встроенный способ проверить вложенность — a.contains(b).
Соответствующий узел в клоне
function getPath(root, node) {
const path = [];
for (let current = node; current !== root; current = current.parentNode) {
path.unshift([...current.parentNode.childNodes].indexOf(current));
}
return path;
}
function findByPath(root, path) {
return path.reduce((node, index) => node.childNodes[index], root);
}
function findCorresponding(rootA, rootB, nodeA) {
return findByPath(rootB, getPath(rootA, nodeA));
}
const clone = document.body.cloneNode(true);
const original = document.querySelector("#price");
findCorresponding(document.body, clone, original); // тот же элемент в копииСобрать текст и посчитать глубину
function collectText(node) {
if (node.nodeType === Node.TEXT_NODE) return node.textContent;
return [...node.childNodes].map(collectText).join(""); // то же делает node.textContent
}
function maxDepth(element) {
if (element.children.length === 0) return 1;
return 1 + Math.max(...[...element.children].map(maxDepth));
}Встроенный TreeWalker
const walker = document.createTreeWalker(document.body, NodeFilter.SHOW_TEXT);
const texts = [];
while (walker.nextNode()) texts.push(walker.currentNode.textContent.trim());Доп. вопросы интервьюера
childrenvschildNodes?children— только элементы,childNodes— также текст и комментарии.HTMLCollectionvsNodeList?getElementsBy*возвращают «живую» коллекцию,querySelectorAll— статическийNodeList.- DFS или BFS? DFS — порядок документа; BFS (очередь) — по уровням, например найти ближайший к корню элемент.
- Сложность? O(n) по числу узлов.
Что важно помнить
- Решение — обычный обход дерева; DOM — частный случай дерева.
- Сохраняйте порядок документа, если это важно для задачи.
- Для глубоких деревьев используйте итеративный обход.
- Теория: DFS и BFS для дерева.
Мини-шпаргалка
Поиск по классу: DFS по children + classList.contains. Общий предок: Set предков первого узла, подъем от второго. Узел в клоне: путь индексов childNodes от корня. children — элементы, childNodes — все узлы. Встроенно — TreeWalker, contains.
Документация
MDN: Element.children, MDN: Node.childNodes, MDN: Document.createTreeWalker(), MDN: Node.contains().