前端手写题之 树 场景题 js
本人github链接 求follow
前端手写题集锦 use js 记录大厂面试常考手写题，github仓库地址：https://github.com/Sunny-117/Front-end-handwritten-question。伴随秋招陆续更新，求star
前端手写题系列文章： 前端手写题之正则表达式 前端手写题之 树 场景题 js 前端手写题之JavaScript 原生方法重写
鉴于现在的手写题还有笔试题都常考树形结构，本人面试笔试也遇到很多，所以总结了以下几个题，几乎覆盖所有笔面试场景，希望对uu们有用
如果认为题解有问题或者不是最优解，欢迎提issue
DOM2JSON
{
tag: 'DIV',
children: [
{
tag: 'SPAN',
children: [
{ tag: 'A', children: [] }
]
},
{
tag: 'SPAN',
children: [
{ tag: 'A', children: [] },
{ tag: 'A', children: [] }
]
}
]
}
function dom2Json(domtree) {
let obj = {};
obj.name = domtree.tagName;
obj.children = [];
domtree.childNodes.forEach((child) => obj.children.push(dom2Json(child)));
return obj;
}
将虚拟 Dom 转化为真实 Dom
{
tag: 'DIV',
attrs:{
id:'app'
},
children: [
{
tag: 'SPAN',
children: [
{ tag: 'A', children: [] }
]
},
{
tag: 'SPAN',
children: [
{ tag: 'A', children: [] },
{ tag: 'A', children: [] }
]
}
]
}
把上诉虚拟Dom转化成下方真实Dom
<div id="app">
<span>
<a></a>
</span>
<span>
<a></a>
<a></a>
</span>
</div>
// 真正的渲染函数
function _render(vnode) {
// 如果是数字类型转化为字符串
if (typeof vnode === "number") {
vnode = String(vnode);
}
// 字符串类型直接就是文本节点
if (typeof vnode === "string") {
return document.createTextNode(vnode);
}
// 普通DOM
const dom = document.createElement(vnode.tag);
if (vnode.attrs) {
// 遍历属性
Object.keys(vnode.attrs).forEach((key) => {
const value = vnode.attrs[key];
dom.setAttribute(key, value);
});
}
// 子数组进行递归操作
vnode.children.forEach((child) => dom.appendChild(_render(child)));
return dom;
}
计算目录树的深度
const tree = {
name: 'root',
children: [
{ name: '叶子1-1' },
{ name: '叶子1-2' },
{
name: '叶子2-1',
children: [{
name: '叶子3-1',
children: [{
name: '叶子4-1',
children: [{}]
}]
}]
}
]
}
function getLevel(tree) {
if (tree == null) return 0;
const queue = [tree]
let dep = 0;
while (queue.length) {
dep++;
const size = queue.length
for (let i = 0; i < size; i++) {
const node = queue.shift()
if (node.children) {
for (const child of node.children) {
queue.push(child)
}
}
}
}
return dep
}
console.log(getLevel(tree));
树形结构获取路径名
const treeData = [
{
name: "root",
children: [
{ name: "src", children: [{ name: "index.html" }] },
{ name: "public", children: [] },
],
},
];
const RecursiveTree = (data) => {
const res = []
const dfs = (data) => {
data.forEach(ele => {
res.push(ele.name)
ele.children && dfs(ele.children)
});
}
dfs(data)
return res;
}
console.log(RecursiveTree(treeData));
树形结构转成列表
const data = [
{
id: 1,
text: '节点1',
parentId: 0,
children: [
{
id: 2,
text: '节点1_1',
parentId: 1
}
]
}
]
//直接放，删除逻辑
function treeToList(data) {
let res = [];
const dfs = (tree) => {
tree.forEach((item) => {
if (item.children) {
dfs(item.children);
delete item.children;
}
res.push(item);
});
};
dfs(data);
return res;
}
//直接放需要的，我写的
function treeToList(data) {
const res = []
function dfs(data) {
const obj = {}
data.forEach(ele => {
obj.id = ele.id
obj.text = ele.text
obj.parentId = ele.parentId
ele.children && dfs(ele.children)
});
res.push(obj)
}
dfs(data)
return res;
}
console.log(treeToList(data));
列表转成树形结构
const rootList = [
{ id: 1, parent: null, text: "菜单1" },
{ id: 11, parent: 1, text: "菜单1-1" },
{ id: 12, parent: 1, text: "菜单1-2" },
{ id: 2, parent: null, text: "菜单2" },
{ id: 21, parent: 2, text: "菜单2-1" },
];
function getTreeList(rootList, id, list) {
for (const item of rootList) {
if (item.parent === id) {
list.push(item);
}
}
for (const i of list) {
i.children = [];
getTreeList(rootList, i.id, i.children);
if (i.children.length === 0) {
delete i.children;
}
}
return list;
}
const res = getTreeList(rootList, null, []);
console.log("res", res);
对象树遍历
const tree = {
name: 'root',
children: [
{
name: 'c1',
children: [
{
name: 'c11',
children: []
},
{
name: 'c12',
children: []
}
]
},
{
name: 'c2',
children: [
{
name: 'c21',
children: []
},
{
name: 'c22',
children: []
}
]
}
]
}
// 深度优先的方式遍历 打印 name
// ['root', 'c1','c11', 'c12', 'c2', 'c21', 'c22']
// 我写的
function solve(root) {
const res = []
function dfs(root) {
for (const key in root) {
if (key === 'name') {
res.push(root[key])
} else if (key === 'children') {
root[key].forEach(ele => {
dfs(ele)
});
}
}
}
dfs(root)
return res;
}
console.log(solve(tree));
获取树对象属性
var tree = {
name: '中国',
children: [
{
name: '北京',
children: [
{
name: '朝阳群众'
},
{
name: '海淀区'
},
{
name: '昌平区'
}
]
},
{
name: '浙江省',
children: [
{
name: '杭州市',
code: '0571',
},
{
name: '嘉兴市'
},
{
name: '绍兴市'
},
{
name: '宁波市'
}
]
}
]
};
function fn(tree, name) {
const obj = {}
function dfs(tree) {
for (const key in tree) {
if (tree.name === name) {
obj[key] = tree[key]
} else {
tree.children && tree.children.forEach(ele => {
dfs(ele)
});
}
}
}
dfs(tree)
return obj
}
function fn(tree, name) {
//bfs
let Queue = [[tree.name, tree.children]];
while (Queue.length > 0) {
//出队当前节点
let cur = Queue.shift();
if (cur[0] === name) return { name: name, code: cur[1] }
//将children入队
if (cur.length === 1) continue;
for (let node of cur[1]) {
let obj = [node.name];
if (node.hasOwnProperty("children")) obj.push(node.children);
if (node.hasOwnProperty("code")) obj.push(node.code);
Queue.push(obj);
}
}
return -1;
}
var node = fn(tree, '杭州市');
console.log(node); // { name: '杭州市', code: 0571 }
查找json中的children路径 现有如下json（简化为对象），已知每个节点id唯一，编写findNode(id)，返回路径，如findNode(5 输出 1->4->5
json = {
id: 1,
children: [
{ id: 2, children: [{ id: 3, children: [] }] },
{
id: 4,
children: [
{ id: 5, children: [] },
{ id: 6, children: [] },
],
},
{ id: 7, children: [] },
],
};
let result = []
// 独立完成
function findNode(obj) {
const res = []
function dfs(obj, currPath, target) {
if (!obj) return;
if (obj.id === target) {
currPath += obj.id
res.push(currPath)
return
}
currPath += obj.id + '->'
obj.children && obj.children.forEach(ele => {
dfs(ele, currPath, target)
});
}
dfs(obj, '', 5)
return res;
}
console.log(findNode(json));
对象字符串转化成树形结构
let strarr = {
'a-b-c-d':1,
'a-b-c-e':2,
'a-b-f':3,
'a-j':4
}
let obj = {
a:{
b:{
c:{
d:1,
e:2
},
f:3
},
j:4
}
}
function parse(obj) {
let ans = {}
for (let att in obj) {
let temp = ans;
for (let i = 0, len = att.length; i < len; i += 2) {
let cur = att[i];
if (i == len - 1) {
temp[cur] = obj[att];
} else {
if (!temp[cur]) {
temp[cur] = {};
}
temp = temp[cur];
}
}
}
return ans;
}
判断有无符合路径和 -> 打印所有路径
const data3 = [
{
id: 1,
name: '前端',
children: [
{
id: 2,
name: 'html',
children: [
{ id: 5, name: 'vue', children: [] },
{ id: 6, name: 're', children: [] },
]
},
{
id: 3,
name: 'html',
children: [
{ id: 7, name: 'vue', children: [] },
{ id: 8, name: 're', children: [] },
]
}
]
}
]
function findData(data, id = 1) {
let queue = [data[0]]
let map = new Map()
map.set(data[0], [data[0].name])
while (queue.length) {
let length = queue.length
for (let i = 0; i < length; i++) {
let node = queue.shift()
for (let i = 0; i < node.children.length; i++) {
if (node.children[i].id === id) {
return [...map.get(node), node.children[i].name].join('-')
} else {
queue.push(node.children[i])
map.set(node.children[i], [...map.get(node), node.children[i].name])
}
}
}
console.log(map);
}
}
console.log(findData(data3, 5));//前端-html-vue
#算法##前端工程师##秋招##如何反向拿捏领导##后端开发实习生#
