likes
comments
collection
share

2023 校招提前批预备！7个题，拿下“树型结构“编程题

作者站长头像
站长
· 阅读数 14

本文提取了js-challenges中“树”专题的部分典型题目，从题目的前端实际应用场景，到思路分析和题解，最后分析了题解的时空复杂度。

2023 校招提前批预备！7个题，拿下“树型结构“编程题

1. JSON2DOM

题目要求

要求实现 json2dom 方法，该方法接收一个 JavaScript 对象作为参数，该对象的结构如下：

const domtree = {
  tag: "div",
  props: {
    id: "myDiv",
    class: "container",
  },
  children: [
    "Hello,",
    {
      tag: "span",
      props: {
        style: "color: blue;",
      },
      children: ["World!"],
    },
  ],
};

// 创建真实的DOM节点
const realDOM = json2dom(domtree);

// 将DOM节点添加到页面中
document.body.appendChild(realDOM);

要求该函数返回结果是一个真实的 DOM，并且 DOM 的结构与给定的 JavaScript 对象相匹配。

前端场景

这个题目的背景是与前端框架（如 React 和 Vue）中的虚拟 DOM（Virtual DOM）相关的。在这些框架中，为了提高性能并实现高效的页面更新，通常会使用虚拟 DOM 的概念。

虚拟 DOM 是指使用 JavaScript 对象来表示真实的 DOM 结构，这些对象通常被称为虚拟 DOM 节点。通过对比前后两个虚拟 DOM 树的差异，框架可以确定需要进行哪些具体的 DOM 操作来更新页面，而不是直接操作真实的 DOM。

在题目中，给定的 JavaScript 对象 domtree 可以被看作是一个虚拟 DOM 树的表示。题目要求你实现一个方法 json2dom，将该虚拟 DOM 树转换为真实的 DOM，并且保持其结构不变。这样可以帮助你理解虚拟 DOM 的概念和实现原理。

React 和 Vue 等前端框架使用虚拟 DOM 来进行高效的页面渲染和更新。它们通过比较前后两个虚拟 DOM 树的差异，然后只对需要更新的部分进行操作，最终将更新的结果应用到真实的 DOM 上，从而减少了直接操作 DOM 的成本。这种方式可以提高性能并改善用户体验。

思路分析

为了将虚拟 DOM 节点转换为真实 DOM 节点，我们可以采用递归的方式遍历虚拟 DOM 树，根据节点类型创建相应的真实 DOM 节点，并设置属性和处理子节点。具体的实现思路如下：

  1. 如果传入的 vnode 是一个字符串，说明它是文本节点，直接创建文本节点并返回。
  2. 否则，解构虚拟 DOM 节点，获取其标签名（tag）、属性（props）和子节点（children）。
  3. 创建一个真实的 DOM 节点，使用标签名创建元素节点（document.createElement）。
  4. 如果虚拟 DOM 节点有属性（props），遍历属性对象，使用setAttribute方法为真实 DOM 节点设置属性。
  5. 如果虚拟 DOM 节点有子节点（children），遍历子节点数组，对每个子节点递归调用创建真实 DOM 节点的函数，并将返回的节点追加到当前节点中。
  6. 返回创建的真实 DOM 节点。

题解

function json2dom(vnode) {
  if (typeof vnode === "string") {
    // 处理文本节点
    return document.createTextNode(vnode);
  }

  const { tag, props, children } = vnode;
  const element = document.createElement(tag);

  // 设置属性
  if (props) {
    for (const [key, value] of Object.entries(props)) {
      element.setAttribute(key, value);
    }
  }

  // 处理子节点
  if (Array.isArray(children)) {
    for (const childVNode of children) {
      const childElement = json2dom(childVNode);
      element.appendChild(childElement);
    }
  }

  return element;
}

最终效果

2023 校招提前批预备！7个题，拿下“树型结构“编程题

复杂度分析

时间复杂度

  • 对于单个虚拟 DOM 节点，需要遍历其属性并设置，时间复杂度为 O(k)，其中 k 是属性数量。
  • 对于虚拟 DOM 节点的子节点，需要遍历子节点数组，并递归创建真实 DOM 节点，时间复杂度取决于子节点的数量和结构。

综上所述，总体时间复杂度为 O(n)，其中 n 是虚拟 DOM 节点的总数量。

空间复杂度

  • 递归调用时，每次都会创建新的函数调用帧，所以空间复杂度取决于递归深度。最坏情况下，递归深度等于虚拟 DOM 树的高度，空间复杂度为 O(h)，其中 h 是虚拟 DOM 树的高度。

2. DOM2JSON

题目要求

要求实现 dom2json 方法，该方法接收一个真实的 DOM 节点作为参数，将其转换为一个 JavaScript 对象表示的虚拟 DOM 树。

<div id="app">
  <span>
    <a></a>
  </span>
  <span>
    <a demo="123"></a>
    <a></a>
  </span>
</div>
<script>
  const node = document.getElementById("app");
  const res = dom2json(node);
  console.log(res); // json
</script>

Output:

{
  "tag": "DIV",
  "props": {
    "id": "app"
  },
  "children": [
    {
      "tag": "SPAN",
      "children": [
        {
          "tag": "A"
        }
      ]
    },
    {
      "tag": "SPAN",
      "children": [
        {
          "tag": "A",
          "props": {
            "demo": "123"
          }
        },
        {
          "tag": "A"
        }
      ]
    }
  ]
}

前端场景

此题目和第一题“JSON2DOM”类似

思路分析

在实现 dom2json 方法时，我们需要遍历给定的 DOM 节点及其子节点，并将其属性和子节点信息转换为 JavaScript 对象的属性和子属性。具体思路如下：

  1. 创建一个空的 JavaScript 对象，用于表示虚拟 DOM 树。
  2. 将 DOM 节点的标签名作为虚拟 DOM 节点的 tag 属性值。
  3. 如果 DOM 节点具有属性，遍历属性列表，将属性名和属性值存储到虚拟 DOM 节点的 props 属性中。
  4. 处理子节点

在处理子节点时，我们首先使用 Array.from 将 DOM 节点的 childNodes 转换为一个真正的数组 childNodes。这是因为 childNodes 返回的是一个类数组对象，使用 Array.from 可以将其转换为一个可以使用数组方法的数组。

然后，我们使用 filter 方法对 childNodes 数组进行过滤，将满足以下条件的子节点保留下来：

  • 节点类型为 1，表示元素节点。
  • 节点类型为 3，表示文本节点，并且其文本内容经过 textContent.trim() 后不为空白。

通过这个过滤，我们可以排除空白文本节点，并只保留元素节点和非空白文本节点。

接下来，如果经过过滤后的子节点数组 filteredChildNodes 的长度大于 0，说明存在满足条件的子节点。我们将对每个满足条件的子节点应用递归调用 dom2json 方法，将其转换为虚拟 DOM 节点，并存储在 vnode 的 children 属性中。

这样，我们完成了对子节点的处理，并将转换后的虚拟 DOM 节点存储在父节点的 children 属性中，构建了完整的虚拟 DOM 树的结构。

  1. 返回最终的虚拟 DOM 树对象。

题解

function dom2json(node) {
  const vnode = {};

  // 处理标签名
  vnode.tag = node.tagName;

  // 处理属性
  if (node.attributes?.length > 0) {
    vnode.props = {};
    for (const attr of node.attributes) {
      vnode.props[attr.name] = attr.value;
    }
  }

  // 处理子节点
  const childNodes = Array.from(node.childNodes);
  const filteredChildNodes = childNodes.filter((childNode) => {
    return (
      childNode.nodeType === 1 || // 元素节点
      (childNode.nodeType === 3 && childNode.textContent.trim() !== "") // 非空白文本节点
    );
  });
  if (filteredChildNodes.length > 0) {
    vnode.children = filteredChildNodes.map((childNode) => {
      return dom2json(childNode);
    });
  }

  return vnode;
}

复杂度分析

时空复杂度都同理于第一题 JSON2DOM

3. 计算目录树的深度

题目要求

请实现一个函数 getTreeDepth(tree)，用于计算给定目录树的深度（层级），分别采用深度优先搜索（DFS）算法和广度优先搜索（BFS）算法来完成。

目录树结构如下：

const tree = {
  name: "root",
  children: [
    { name: "叶子1-1" },
    { name: "叶子1-2" },
    {
      name: "叶子2-1",
      children: [
        {
          name: "叶子3-1",
          children: [
            {
              name: "叶子4-1",
              children: [{}],
            },
          ],
        },
      ],
    },
  ],
};

函数接收一个目录树 tree 作为参数，该目录树采用对象表示，每个节点包含一个 name 属性表示节点名称，以及一个 children 属性表示子节点列表。子节点列表可能为空。

函数应该返回目录树的深度（层级）作为结果。

示例：

const tree = {
  name: "root",
  children: [
    { name: "叶子1-1" },
    { name: "叶子1-2" },
    {
      name: "叶子2-1",
      children: [
        {
          name: "叶子3-1",
          children: [
            {
              name: "叶子4-1",
              children: [{}],
            },
          ],
        },
      ],
    },
  ],
};

const depth = getTreeDepth(tree);
console.log(depth); // 输出: 5

变形题：计算普通 n 维数组的深度（快手面试题）

前端场景

  1. 导航菜单的层级控制：在构建导航菜单时，可以根据目录树的深度来控制菜单的层级显示。这有助于实现多级嵌套的导航菜单结构。
  2. 树状组件的展开和折叠：对于树状结构的组件（例如树形视图、文件资源管理器等），可以使用目录树的深度来确定初始展开的层级，并提供展开和折叠的功能。
  3. 面包屑导航的生成：面包屑导航是一种显示当前页面路径的导航方式，可以根据目录树的深度生成相应的面包屑导航路径。
  4. 页面布局和样式的层级控制：在前端开发中，可能会根据目录树的深度来确定页面布局和样式的层级关系，以实现不同层级的元素叠加、覆盖等效果

思路分析和题解

DFS

  1. 如果目录树为空，返回 0。
  2. 初始化一个变量 maxDepth 为 0，用于记录最大深度。
  3. 对于每个子节点，递归调用 getTreeDepthDFS 函数计算其深度，将其返回的深度与 maxDepth 进行比较，更新 maxDepth 为较大值。
  4. 返回 maxDepth + 1，即为目录树的深度。

代码实现：

function getTreeDepth(tree) {
  if (!tree) return 0;
  let maxLevel = 0;

  function traverse(node, level) {
    if (!node.children || node.children.length === 0) {
      maxLevel = Math.max(maxLevel, level);
      return;
    }

    for (const child of node.children) {
      traverse(child, level + 1);
    }
  }

  traverse(tree, 1);

  return maxLevel;
}

BFS

采用 BFS 算法的思路是按层级遍历目录树的节点，利用队列数据结构来实现。

具体实现步骤如下：

  1. 如果目录树为空，返回 0。
  2. 创建一个队列，并将根节点入队。
  3. 初始化一个变量 level 为 1，用于记录当前的层级。
  4. 进入循环，直到队列为空：
    • 获取当前队列中的节点数量，该数量表示当前层级的节点数。
    • 遍历当前层级的节点数：
      • 出队一个节点。
      • 如果节点存在子节点，则将子节点入队。
    • 增加 level 的值。
  5. 返回 level - 1，即为目录树的深度。

代码实现：

function getTreeDepth(tree) {
  if (!tree) return 0;

  const queue = [tree];
  let level = 1;

  while (queue.length > 0) {
    const levelSize = queue.length;

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();

      if (node.children?.length > 0) {
        for (const child of node.children) {
          queue.push(child);
        }
      }
    }

    level++;
  }

  return level - 1;
}

复杂度分析

  • DFS 时间复杂度：O(n)，其中 n 是目录树的节点数。在 DFS 中，我们会遍历每个节点一次，因此时间复杂度与节点数量成正比。
  • DFS 空间复杂度：O(h)，其中 h 是目录树的高度。在 DFS 中，递归调用会产生函数调用栈，其空间复杂度取决于递归的深度，即树的高度。
  • BFS 时间复杂度：O(n)，其中 n 是目录树的节点数。在 BFS 中，我们会访问每个节点一次，因此时间复杂度与节点数量成正比。
  • BFS 空间复杂度：O(m)，其中 m 是目录树同一层级的最大节点数。在 BFS 中，我们需要使用队列来存储同一层级的节点，最坏情况下，队列的大小取决于同一层级的最大节点数。

4. 树形结构转成列表

题目要求

实现一个函数 flattenTree(data)，用于将给定的树形结构转换成列表形式。树形结构由 JavaScript 对象数组表示，每个对象包含 id、text 和 parentId 属性，以及可选的 children 属性。函数应该返回转换后的结果列表的 JSON 字符串形式。

const data = [
  {
    id: 1,
    text: "节点1",
    parentId: 0,
    children: [
      {
        id: 2,
        text: "节点1_1",
        parentId: 1,
      },
    ],
  },
];

const flattenTree = (data) => {};
const flattenedData = flattenTree(data);
console.log(flattenedData);
// [
//     { id: 1, text: '节点1', parentId: 0 },
//     { id: 2, text: '节点1_1', parentId: 1 }
//  ]

前端场景

在前端开发中，树形结构常用于表示菜单、导航栏、分类等具有层级关系的数据。将树形结构转换为列表形式可以方便地进行展示和处理，例如用于生成树状列表组件、进行数据筛选和搜索等操作。

思路分析和题解

DFS

定义一个空数组 result 用于存储转换后的列表数据。 定义一个递归函数 traverse，用于遍历树的每个节点。 在 traverse 函数中，将当前节点的 id、text 和 parentId 属性提取出来，并将其作为一个对象存入 result 数组中。 如果当前节点有子节点，则对每个子节点递归调用 traverse 函数。 在主函数中，遍历输入的树形结构数据数组，对每个根节点调用 traverse 函数。 返回 result 数组的 JSON 字符串形式作为结果。

const flattenTree = (data) => {
  const result = [];

  const traverse = (node) => {
    const { id, text, parentId, children } = node;
    result.push({ id, text, parentId });

    if (children && children.length > 0) {
      for (const child of children) {
        traverse(child);
      }
    }
  };

  for (const node of data) {
    traverse(node);
  }

  return result;
};

BFS

BFS 使用队列来存储待处理的节点。初始时，将树的根节点加入队列。然后进行循环迭代，直到队列为空。

在每次迭代中，从队列中取出一个节点，并将其 id、text 和 parentId 属性添加到结果数组中。然后检查该节点是否有子节点，如果有，则将每个子节点与路径（即从根节点到当前节点的路径）一起加入队列。路径是一个数组，用于记录当前节点的祖先节点的 id。

const flattenTree = (data) => {
  const result = [];
  const queue = [];

  for (const node of data) {
    queue.push({ node, path: [] });
  }

  while (queue.length > 0) {
    const { node, path } = queue.shift();
    const { id, text, parentId, children } = node;

    result.push({ id, text, parentId });

    if (children && children.length > 0) {
      for (const child of children) {
        queue.push({ node: child, path: [...path, id] });
      }
    }
  }

  return result;
};

复杂度分析

DFS

  • 时间复杂度

时间复杂度应为 O(n^2)，其中 n 是树中节点的总数。这是因为在每个节点上都需要遍历其子节点，而在最坏的情况下，每个节点都有子节点，导致遍历过程中需要进行大量的重复工作。

由于每个节点的子节点可能是一个数组，遍历子节点的时间复杂度为 O(m)，其中 m 是子节点的数量。而在最坏情况下，树是一个单侧倾斜的链表结构，每个节点都有一个子节点，因此 m 最大为 n-1。所以总的时间复杂度为 O(n * (n-1)) = O(n^2)。

  • 空间复杂度

递归调用时，会产生函数调用栈，其最大深度取决于树的高度。在最坏情况下，树是一个单侧倾斜的链表结构，高度为 n，因此空间复杂度为 O(n)。

额外使用的空间主要是结果数组 result 和递归调用栈。

BFS

  • 时间复杂度：该解决方案中，我们遍历了每个节点一次，因此时间复杂度为 O(n)，其中 n 是树中节点的总数。

  • 空间复杂度：使用了一个队列来存储待处理的节点，因此空间复杂度为 O(n)，其中 n 是树中节点的总数。

5. 列表转成树形结构

题目要求

实现一个函数 listToTree(arr)，用于将给定的列表转换为树形结构。列表中的每个元素是一个对象，包含 id、name 和 pid 属性，分别表示节点的唯一标识、名称和父节点的标识。函数应返回树形结构的根节点。

let arr = [
  { id: 1, name: "部门1", pid: 0 },
  { id: 2, name: "部门2", pid: 1 },
  { id: 3, name: "部门3", pid: 1 },
  { id: 4, name: "部门4", pid: 3 },
  { id: 5, name: "部门5", pid: 4 },
  { id: 6, name: "部门6", pid: 0 },
];
const listToTree = (list) => {};

const res = listToTree(arr);
console.log(res);

2023 校招提前批预备！7个题，拿下“树型结构“编程题

前端场景

  • 导航菜单：网站或应用程序中的导航菜单通常以树形结构的形式呈现。通过将扁平的菜单数据转换为树形结构，可以更方便地展示层级关系，实现多级菜单的嵌套和展开/折叠功能。

  • 文件目录：在文件管理器或项目管理工具中，可以使用树形结构来展示文件目录。将扁平的文件列表转换为树形结构可以更好地反映文件的层级关系，方便用户浏览和管理文件。

  • 组织架构：在企业管理系统或人事管理系统中，组织架构通常以树形结构的形式展示。通过将员工或部门的数据转换为树形结构，可以展示组织的层级关系，帮助用户查看和管理组织结构。

  • 评论回复：在社交媒体或论坛等平台上，用户可以对评论进行回复。通过将评论数据转换为树形结构，可以呈现出回复的层级结构，使用户能够清晰地查看评论和回复之间的关联关系。

  • 可视化图表：某些可视化图表，如树图、组织架构图等，需要使用树形结构的数据进行展示。将数据转换为树形结构可以更方便地在可视化库或图表组件中使用。

总之，将列表转换为树形结构在我们的前端开发中非常常见，广泛应用于导航菜单、文件目录、组织架构、评论回复以及可视化图表等场景，以便更好地展示和操作具有层级关系的数据。

思路分析

先创建一个节点映射 map，然后通过两次遍历实现将列表转换为树形结构。第一次遍历用于构建节点映射关系和初始化节点的 children 属性，第二次遍历根据节点的 pid 找到对应的父节点，并将当前节点添加到父节点的 children 数组中，或者将当前节点作为根节点添加到 treeData 数组中

题解

const listToTree = (list) => {
  const map = new Map();
  const treeData = [];
  for (let i = 0; i < list.length; i++) {
    const node = list[i];
    const { id, pid } = node;
    node.children = [];

    map.set(id, i);

    if (pid) {
      const parentIndex = map.get(pid);
      if (parentIndex !== undefined) {
        list[parentIndex].children.push(node);
      }
    } else {
      treeData.push(node);
    }
  }
  return treeData;
};

复杂度分析

时间复杂度

该解决方案的时间复杂度为 O(n)，其中 n 是列表的长度。在遍历列表创建节点和构建树的过程中，每个节点只被访问一次。

空间复杂度

使用了一个对象 idToNodeMap 来存储节点，并且构建的树形结构中只保留了根节点的引用。因此，空间复杂度为 O(n)，其中 n 是列表的长度。

6. 根据 id 从多叉树里面查找出对应的节点的 name

题目要求

给定一个多叉树 tree 和一个节点的 ID id，编写一个函数 findNodeNameById，用于在多叉树中查找指定节点 ID 对应的节点名称。如果找到节点，则返回节点名称；如果未找到，则返回 null。

const tree = {
  name: "root",
  id: 1,
  children: [
    {
      name: "c1",
      id: 2,
      children: [
        {
          name: "c11",
          id: 3,
          children: [],
        },
        {
          name: "c12",
          id: 4,
          children: [],
        },
      ],
    },
    {
      name: "c2",
      id: 5,
      children: [
        {
          name: "c21",
          id: 6,
          children: [],
        },
        {
          name: "c22",
          id: 7,
          children: [],
        },
      ],
    },
  ],
};

const nodeName = findNodeNameById(tree, 3);
console.log(nodeName); // 'c11'

前端场景

在前端开发中，经常会遇到处理多叉树结构的情况，例如组织架构、菜单导航等。在这些场景中，有时候需要根据节点的 ID 查找节点的相关信息，比如节点的名称、URL 等。这个题目模拟了这样的需求，通过编写一个函数实现根据节点 ID 查找节点名称的功能。

思路分析

我们可以利用深度优先遍历和一个哈希表来实现该功能。具体思路如下：

  • 初始化一个空的哈希表 idToNameMap，用于存储节点的 ID 和名称的映射关系。

  • 定义一个深度优先遍历的函数 dfs，用于遍历多叉树的节点。

  • 在 dfs 函数中，将当前节点的 ID 和名称存储到 idToNameMap 哈希表中。

  • 如果当前节点有子节点，则递归调用 dfs 函数遍历子节点。

  • 在主函数 findNodeNameById 中，首先调用 dfs 函数对多叉树进行深度优先遍历，将所有节点的 ID 和名称存储到 idToNameMap 哈希表中。

  • 根据给定的节点 ID，从 idToNameMap 哈希表中查找对应的节点名称。

  • 如果找到节点名称，则返回节点名称；否则，返回 null。

题解

const findNodeNameById = (tree, id) => {
  const idToNameMap = {};
  const dfs = (node) => {
    idToNameMap[node.id] = node.name;
    if (node.children && node.children.length > 0) {
      for (const child of node.children) {
        dfs(child);
      }
    }
  };
  dfs(tree);
  return idToNameMap[id] || null;
};

7. 查找 json 中的 children 路径

题目要求

现有如下 json 对象，已知每个节点 id 唯一，编写 findNode(id)，返回路径，如 findNode(5) 输出 1->4->5

const json = {
  id: 1,
  children: [
    { id: 2, children: [{ id: 3, children: [] }] },
    {
      id: 4,
      children: [
        { id: 5, children: [] },
        { id: 6, children: [] },
      ],
    },
    { id: 7, children: [] },
  ],
};

前端场景

在前端开发中，处理树形结构的数据是常见的情况，例如导航菜单、文件目录等。有时候需要根据节点的 ID 查找从根节点到目标节点的路径，以便进行相关操作或展示。这个题目模拟了这样的需求，通过编写一个函数实现查找路径的功能。

思路分析

我们可以使用深度优先遍历（DFS）的方式来实现查找路径的功能。具体思路如下：

定义一个空数组 path，用于存储节点的 ID。 定义一个深度优先遍历的函数 dfs，用于遍历 JSON 对象的节点。 在 dfs 函数中，首先将当前节点的 ID 加入 path 数组。 如果当前节点的 ID 等于目标节点的 ID，则找到了目标节点，停止遍历。 如果当前节点有子节点，则递归调用 dfs 函数遍历子节点。 在主函数 findNode 中，调用 dfs 函数对 JSON 对象进行深度优先遍历，查找目标节点的路径。 将 path 数组转换为字符串，使用箭头 "->" 连接所有节点 ID，得到最终的路径。

题解

const findNode = (json, id) => {
  let path = [];
  const dfs = (node) => {
    path.push(node.id);
    if (node.id === id) {
      return;
    }
    if (node.children?.length > 0) {
      for (const child of node.children) {
        dfs(child);
        if (path[path.length - 1] === id) {
          return;
        }
      }
    }
    path.pop();
  };

  dfs(json);

  return path.join("->");
};