这是一道腾讯的面试题，求大神解答一下~
之前描述题目可能不太仔细，仔细的说一下整个题目：
应聘岗位：web前端开发
问题：
有一个html文档，有十万个节点：
极客观点
项目管理
HarmonyOS
HTML
body
节点1
节点1.2
节点2
节点2.1
节点2.2
节点2.3
...
...
节点5
节点5.2
节点5.3
节点5.3.1
节点5.3.2
...
面试官说的考察重点是：算法以及性能优化那一部分
这道题应该怎么解答呢？
因你没有提及面试的岗位及要求, 这里假设是前端面试.
怎么在有十万个节点的html文档中找到特定的某个节点
根据该节点的属性, 从以下方法中选择最精准匹配的一个
getElementById
getElementsByName
getElementsByTagName
getElementsByClassName
querySelector
querySelectorAll我的思路是用css的nth-child()选择器做筛选。
<!--html部分，嵌套的元素没有id和class，也没有任何属性值。-->
<body>
<div>
<header>
<nav>
<h1>
<a></a>
</h1>
<h3>
<p></p>
</h3>
</nav>
</header>
<div>
<section>
<article>
<h2><a></a></h2>
<div><p></p></div>
<p><span></span></p>
</article>
</section>
<section>
<article>
<h2><a></a></h2>
<div>
<div>
<div>
<header>
<nav>
<h1>
<a></a>
</h1>
<h3>
<p></p>
</h3>
</nav>
</header>
<div>
<section>
<article>
<h2><a></a></h2>
<div><p></p></div>
<p><span></span></p>
</article>
</section>
<section>
<article>
<h2><a></a></h2>
<div>
<p>target</p>
</div>
<p><span></span></p>
</article>
</section>
<section>
<article>
<h2><a></a></h2>
<div><p></p></div>
<p><span></span></p>
</article>
</section>
<section>
<article>
<h2><a></a></h2>
<div><p></p></div>
<p><span></span></p>
</article>
</section>
<section>
<article>
<h2><a></a></h2>
<div><p></p></div>
<p><span></span></p>
</article>
</section>
</div>
<footer>
<span><a></a></span>
<span><a></a></span>
<span><a></a></span>
<span><a></a></span>
<span><a></a></span>
</footer>
</div>
</div>
</div>
<p><span></span></p>
</article>
</section>
<section>
<article>
<h2><a></a></h2>
<div><p></p></div>
<p><span></span></p>
</article>
</section>
<section>
<article>
<h2><a></a></h2>
<div><p></p></div>
<p><span></span></p>
</article>
</section>
<section>
<article>
<h2><a></a></h2>
<div><p></p></div>
<p><span></span></p>
</article>
</section>
</div>
<footer>
<span><a></a></span>
<span><a></a></span>
<span><a></a></span>
<span><a></a></span>
<span><a></a></span>
</footer>
</div>
</body>// js部分
function isString (target) {
return typeof target === 'string';
}
function findNode (parent, child) {
if (!(isString(parent) && isString(child))) {
return;
}
const path = child.split('.');
let str = `${parent}>*`;
for (let i = 0, len = path.length; i < len; i++) {
str += `:nth-child(${path[i]})${i === len - 1 ? '' : '>*'}`;
}
//body>*:nth-child(1)>*:nth-child(2)>*:nth-child(2)>*:nth-child(1)>*:nth-
//child(2)>*:nth-child(1)>*:nth-child(1)>*:nth-child(2)>*:nth-child(2)>*:nth-
//child(1)>*:nth-child(2)>*:nth-child(1)
console.log(str);
return document.querySelector(str);
}
console.log(findNode('body', '1.2.2.1.2.1.1.2.2.1.2.1')); //<p>target</p>这肯定不是最好的解法，因为还是需要做遍历，如果目标节点的位置嵌套过深，例如上万的嵌套，那么按上面那样逐个输入位置就肯定不行了，同时性能估计也很差。
感觉楼上说的二叉树遍历比较接近题目的要求，算法方面我自己也不是很熟，只能想到这个方法。
光从算法层面的话，假设文档是一棵Root节点为html标签的一棵树，因为是只需要返回第一个找到的节点，所以通过队列实现广度优先遍历。如果用querySelector的话，实际上整棵树都被遍历了。
问题1:
function isWanted(node) {
//查找成立的条件
}
function findNode(isWanted) {
const root = document.getElementByTagName('html');
const queue = [root];
while(!isWanted(queue[0])) {
const current = queue[0];
const children = queue[0].children || [];
for(i = 0; i < children.length; i++) {
// 这里在遍历的过程中新增指针把children指向parent, 可以帮助求解第二问。
children[i].parent = current;
queue.push(children[i]);
}
queue.unshift();
}
return queue[0];
}
问题2:
根据第一题找到的node，然后可以找到parent节点，再通过parent找到所有子节点，对应index位置插入节点就好。
function insertNode(newNode) {
const newChildren = [];
const existingNode = findNode(isWanted);
const parent = existingNode.parent;
const siblings = parent.children;
// 如果用indexOf再加上splice的话，需要两次循环。时间复杂度为O(2n)？
for(i = 0; i < siblings; i++) {
if (siblings[i] === existingNode) {
newChildren.push(newNode);
}
newChildren.push(siblings[i]);
}
parent.children = newChildren;
return;
}
1.某个特定的节点是什么意思？比如十万个节点中，找到第一千个p标签这种意思吗？这样的话直接document.getElementByTagName(＂p＂)[999]就行了吧。
当然我有可能没理解对题的意思，不对勿喷。