目录

实现一个LRU缓存

求环状链表

 树的前序、中序、后序遍历

 树的层序遍历

获取树的层级

实现 类数组转数组

实现 DOM转JSON

实现 JSON转DOM

实现 树转数组

实现 数组转树

实现 对象打平

获取树的层级是指确定树中节点的深度，也就是从根节点到该节点的路径长度。可以使用递归或迭代的方式实现。

以下是一个简单的JavaScript实现获取树的层级的示例代码：

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function getTreeDepth(root) {
  if (!root) return 0;
  const leftDepth = getTreeDepth(root.left);
  const rightDepth = getTreeDepth(root.right);
  return Math.max(leftDepth, rightDepth) + 1;
}

在这个实现中，TreeNode类表示树节点，包含一个值val和左右子节点left和right。getTreeDepth函数实现了获取树的层级。这个函数接受一个根节点root作为参数，并返回一个整数，表示树的深度。

使用这个实现，可以创建一个树，并获取其深度。例如，可以使用以下代码创建一个包含5个节点的树，并输出树的深度：

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log(getTreeDepth(root)); // 3

实现 类数组转数组​​​​​​​

类数组转数组是指将类数组对象转换为真正的数组对象。类数组对象是指具有length属性和按照数字索引访问元素的对象，例如arguments对象和DOM元素集合。可以使用Array.from方法或展开运算符（...）实现类数组转数组。

以下是一个简单的JavaScript实现类数组转数组的示例代码：

function toArray(arrayLike) {
  return Array.from(arrayLike);
  // 或者使用展开运算符
  // return [...arrayLike];
}

在这个实现中，toArray函数接受一个类数组对象arrayLike作为参数，并返回一个真正的数组对象。可以使用Array.from方法或展开运算符将类数组对象转换为数组对象。

使用这个实现，可以将一个类数组对象转换为数组对象。例如，可以使用以下代码将arguments对象转换为数组对象：

function foo() {
  const args = toArray(arguments);
  console.log(args);
}

foo(1, 2, 3); // [1, 2, 3]

实现 DOM转JSON

DOM转JSON是指将DOM节点转换为JSON格式的数据。可以使用递归的方式遍历DOM树，将每个节点转换为一个JSON对象，并将所有JSON对象组合成一个JSON数组。

以下是一个简单的JavaScript实现DOM转JSON的示例代码：

function domToJson(node) {
  const obj = {};
  obj.tagName = node.tagName.toLowerCase();
  obj.attributes = {};
  for (let i = 0; i < node.attributes.length; i++) {
    const attr = node.attributes[i];
    obj.attributes[attr.name] = attr.value;
  }
  obj.children = [];
  for (let i = 0; i < node.children.length; i++) {
    const child = node.children[i];
    obj.children.push(domToJson(child));
  }
  return obj;
}

在这个实现中，domToJson函数接受一个DOM节点node作为参数，并返回一个JSON对象。这个函数使用递归的方式遍历DOM树，将每个节点转换为一个JSON对象，并将所有JSON对象组合成一个JSON数组。

使用这个实现，可以将一个DOM节点转换为JSON格式的数据。例如，可以使用以下代码将一个div元素转换为JSON格式的数据：

const div = document.createElement('div');
div.setAttribute('id', 'myDiv');
div.innerHTML = '<p>Hello, world!</p>';

const json = domToJson(div);
console.log(json);

{
  "tagName": "div",
  "attributes": {
    "id": "myDiv"
  },
  "children": [
    {
      "tagName": "p",
      "attributes": {},
      "children": [
        {
          "tagName": "#text",
          "attributes": {},
          "children": [],
          "text": "Hello, world!"
        }
      ]
    }
  ]
}

实现 JSON转DOM

JSON转DOM是指将JSON格式的数据转换为DOM节点。可以使用递归的方式遍历JSON对象，将每个JSON对象转换为一个DOM节点，并将所有DOM节点组合成一个DOM树。

以下是一个简单的JavaScript实现JSON转DOM的示例代码：

实现 树转数组

function jsonToDom(json) {
  const node = document.createElement(json.tagName);
  for (const attr in json.attributes) {
    node.setAttribute(attr, json.attributes[attr]);
  }
  for (let i = 0; i < json.children.length; i++) {
    const child = json.children[i];
    node.appendChild(jsonToDom(child));
  }
  if (json.text) {
    node.appendChild(document.createTextNode(json.text));
  }
  return node;
}

在这个实现中，jsonToDom函数接受一个JSON对象json作为参数，并返回一个DOM节点。这个函数使用递归的方式遍历JSON对象，将每个JSON对象转换为一个DOM节点，并将所有DOM节点组合成一个DOM树。

使用这个实现，可以将一个JSON格式的数据转换为DOM节点。例如，可以使用以下代码将一个JSON格式的数据转换为DOM节点：

const json = {
  "tagName": "div",
  "attributes": {
    "id": "myDiv"
  },
  "children": [
    {
      "tagName": "p",
      "attributes": {},
      "children": [
        {
          "tagName": "#text",
          "attributes": {},
          "children": [],
          "text": "Hello, world!"
        }
      ]
    }
  ]
};

const div = jsonToDom(json);
document.body.appendChild(div);

实现 数组转树

数组转树是指将一个数组转换为树形结构。通常情况下，数组中的每个元素都代表一个节点，节点之间的关系可以通过元素中的某些属性来表示。可以使用递归的方式遍历数组，将每个节点转换为一个树节点，并将所有树节点组合成一个树形结构。

以下是一个简单的JavaScript实现数组转树的示例代码：

function arrayToTree(arr, parentId) {
  const tree = [];
  for (let i = 0; i < arr.length; i++) {
    const node = arr[i];
    if (node.parentId === parentId) {
      const children = arrayToTree(arr, node.id);
      if (children.length) {
        node.children = children;
      }
      tree.push(node);
    }
  }
  return tree;
}

在这个实现中，arrayToTree函数接受一个数组arr和一个父节点ID parentId作为参数，并返回一个树形结构。这个函数使用递归的方式遍历数组，将每个节点转换为一个树节点，并将所有树节点组合成一个树形结构。

使用这个实现，可以将一个数组转换为树形结构。例如，可以使用以下代码将一个数组转换为树形结构

const arr = [
  { id: 1, name: 'Node 1', parentId: null },
  { id: 2, name: 'Node 2', parentId: 1 },
  { id: 3, name: 'Node 3', parentId: 1 },
  { id: 4, name: 'Node 4', parentId: 2 },
  { id: 5, name: 'Node 5', parentId: 2 },
  { id: 6, name: 'Node 6', parentId: 3 },
  { id: 7, name: 'Node 7', parentId: 3 },
];

const tree = arrayToTree(arr, null);
console.log(tree);

[
  {
    "id": 1,
    "name": "Node 1",
    "parentId": null,
    "children": [
      {
        "id": 2,
        "name": "Node 2",
        "parentId": 1,
        "children": [
          {
            "id": 4,
            "name": "Node 4",
            "parentId": 2,
            "children": []
          },
          {
            "id": 5,
            "name": "Node 5",
            "parentId": 2,
            "children": []
          }
        ]
      },
      {
        "id": 3,
        "name": "Node 3",
        "parentId": 1,
        "children": [
          {
            "id": 6,
            "name": "Node 6",
            "parentId": 3,
            "children": []
          },
          {
            "id": 7,
            "name": "Node 7",
            "parentId": 3,
            "children": []
          }
        ]
      }
    ]
  }
]

实现 对象打平

对象打平是指将一个嵌套的对象转换为一个扁平的对象，其中所有的属性都位于同一层级。通常情况下，嵌套的对象中包含了多个层级，每个层级都包含了一些属性。可以使用递归的方式遍历对象，将每个属性转换为一个扁平的属性，并将所有属性组合成一个扁平的对象。

以下是一个简单的JavaScript实现对象打平的示例代码：

function flattenObject(obj, prefix = '') {
  const flatObj = {};
  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      const propName = prefix ? `${prefix}.${key}` : key;
      if (typeof obj[key] === 'object' && obj[key] !== null) {
        Object.assign(flatObj, flattenObject(obj[key], propName));
      } else {
        flatObj[propName] = obj[key];
      }
    }
  }
  return flatObj;
}

在这个实现中，flattenObject函数接受一个嵌套的对象obj和一个前缀prefix作为参数，并返回一个扁平的对象。这个函数使用递归的方式遍历对象，将每个属性转换为一个扁平的属性，并将所有属性组合成一个扁平的对象。

使用这个实现，可以将一个嵌套的对象转换为一个扁平的对象。例如，可以使用以下代码将一个嵌套的对象转换为一个扁平的对象：

const obj = {
  a: {
    b: {
      c: 1,
      d: 2,
    },
    e: 3,
  },
  f: 4,
};

const flatObj = flattenObject(obj);
console.log(flatObj);

{
  "a.b.c": 1,
  "a.b.d": 2,
  "a.e": 3,
  "f": 4
}