k's Learn Notes

手写算法：二叉树的序列化与反序列化

297. 二叉树的序列化与反序列化open in new window

二叉树解题，一般都两种解法，DFS（深度优先搜索）与 BFS（广度优先遍历）

理解题意：

  1. 将二叉树序列化，变成字符串1,2,3,X,X,4,5,X,X,X,X,X

  2. 反序列化，将字符串转换成二叉树

  3. 遇到 null 的时候，转换成'X'

DFS （递归）

序列化

  1. 采用递归的方式，遍历整棵树，只关注当前节点，其余的丢进去再递归遍历。

  2. 选择前序遍历，根 -> 左 -> 右 的打印顺序，在反序列化中更容易定位根节点的值。

// 序列化
function serialize(root) {
  if (root === null) return 'X';

  const left = serialize(root.left);
  const right = serialize(root.right);

  // 按根、左、右的顺序拼接
  return `${root.val},${left},${right}`;
}

反序列化

  1. 得到的是字符串

  2. 定义 buildTree 还原二叉树

  3. 将传进来的字符串，转成数组，依次推出。

  • 推出顺序：根节点、左子树、右子数

  • 判断字符串是否为'X'

    • true，则返回 null
    • false，创建 root 节点，并递归构建左右子树，最后 return root
// 反序列化
function deserialize(data) {
  const list = data.split(',');

  const buildTree = list => {
    const rootVal = list.shift();

    if (rootVal === 'X') return null;
    const root = new TreeNode(rootVal);
    root.left = buildTree(list);
    root.right = buildTree(list);
    return root;
  };

  return buildTree(list);
}

BFS

序列化

  1. 维护一个队列 Q，初始让根节点入列，然后再依次出列：

  • 若出列的是 null，则将'X'推入 res 数组

  • 若是数值，则将节点值推入 res 数组，并将左右节点也分别推入列 Q

    • 若子节点为 null，也要推入'X'
  1. 入列、出列，直到队列 Q 为空，则遍历完所有节点，res 数组构建完毕，转成字符串即可
// 序列化
function serialize(root) {
  let queue = [root];
  let result = [];

  while (queue.length) {
    const node = queue.shift();
    if (node) {
      result.push(node.val);
      queue.push(node.left);
      queue.push(node.right);
    } else {
      result.push('X');
    }
  }
  return result.join(',');
}

反序列化

  1. DFS 得到的是一层层的，那么除了根节点以外，其他的都是成对出现

  2. 判断字符串是否为'X'

  • true，返回 null

  • false，将字符串转成数组，生成根节点 root

  1. 同样维护一个队列 Q，将根节点入列

  2. 初始状态，needle 指针从 1 开始，因为此时根节点已入列

  3. 节点出列，needle 指向左节点，needle+1 指向右节点，判断数值

  • 若为'X'的话，无需操作
  • 若为数值，创建节点，找到父节点拼接起来。同时，自己也是父节点，入列 Q
  • needle 指针加 2，同时考察一对儿子
  1. 依次入列，出列，直到指针长度大于等于数组长度，返回 root
// 反序列化
function deserialize(data) {
  if (data === 'X') return null;
  const list = data.split(',');

  const root = new TreeNode(list[0]);
  let queue = [root];
  let needle = 1;

  while (needle < list.length) {
    const node = queue.shift();

    const leftVal = list[needle];
    const rightVal = list[needle + 1];

    if (leftVal !== 'X') {
      const leftNode = new TreeNode(leftVal);
      node.left = leftNode;
      queue.push(leftNode);
    }

    if (rightVal !== 'X') {
      const rightNode = new TreeNode(rightVal);
      node.right = rightNode;
      queue.push(rightNode);
    }
    needle += 2;
  }
  return root;
}

手写题：使用分片思想优化渲染

题目描述:渲染百万条结构简单的大数据时 怎么使用分片思想优化渲染

暴力法

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>暴力法：解决百万数据，分片渲染</title></title>
</head>
<body>
  <ul id="container"></ul>

  <script>
    // 记录当前时间
    const now = Date.now();
    // 插入十万条数据
    const total = 100000;
    // 获取容器
    const container = document.getElementById('container');

    for(let i = 0; i < total; i++) {
      const li = document.createElement('li');
      // ~~，位运算二进制取反两次，向下取整
      li.innerHTML = ~~(Math.random() * total);
      container.appendChild(li);
    }

    console.log('运行时间:', Date.now() - now);

    // 因为GUI与JS线程是互斥，用setTimeout去计算
    setTimeout(() => {
      console.log('总运行时间:', Date.now() - now);
    });
  </script>
</body>
</html>

时间分片

定时器

从加载任务从一次同步阻塞任务转化成异步任务

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>时间分片-定时器</title></title>
</head>
<body>
  <ul id="container"></ul>

  <script>
    // 获取容器
    const container = document.getElementById('container');
    // 插入十万条数据
    const total = 100000;
    // 第一条记录的索引
    const index = 0;
    // 一页展示的数据
    const size = 20;
    // 总页数
    const page = total / size;

    function loop(curTotal, curIndex) {
      if (curTotal <= 0) return false;

      const pageCount = Math.min(curTotal, size);
      setTimeout(() => {
        for (let i = 0; i < pageCount; i++) {
          const li = document.createElement('li');
          li.innerHTML = `${curIndex + i}: ${~~(Math.random() * total)}`;
          container.appendChild(li);
        };
        loop(curTotal - pageCount, curIndex + pageCount);
      }, 0)

    }

    loop(total, index);
  </script>
</body>
</html>

requestAnimationFrame

将定时的异步操作转化为每一帧渲染的异步操作

它能保证回调函数在屏幕每一次的刷新间隔中只被执行一次，这样不会引发丢帧现象。

与setTimeout相比，requestAnimationFrame最大的优势

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>时间分片-requestAnimationFrame</title></title>
</head>
<body>
  <ul id="container"></ul>

  <script>
    // 获取容器
    const container = document.getElementById('container');
    // 插入十万条数据
    const total = 100000;
    // 第一条记录的索引
    const index = 0;
    // 一页展示的数据
    const size = 20;
    // 总页数
    const page = total / size;

    function loop(curTotal, curIndex) {
      if (curTotal <= 0) return false;

      const pageCount = Math.min(curTotal, size);

      window.requestAnimationFrame(() => {
         for (let i = 0; i < pageCount; i++) {
          const li = document.createElement('li');
          li.innerHTML = `${curIndex + i}: ${~~(Math.random() * total)}`;
          container.appendChild(li);
        };
        loop(curTotal - pageCount, curIndex + pageCount);
      })

    }

    loop(total, index);
  </script>
</body>
</html>

requestAnimationFrame + DocumentFragment

DocumentFragment 优化 Dom 插入

在现在的浏览器中，并不是十分有用，因为现在浏览器的优化已经足够好了。

即使不使用DocumentFragment浏览器也会自动优化插入的 dom

<body>
  <ul id="container"></ul>

  <script>
    // 获取容器
    const container = document.getElementById('container');
    // 插入十万条数据
    const total = 100000;
    // 第一条记录的索引
    const index = 0;
    // 一页展示的数据
    const size = 20;
    // 总页数
    const page = total / size;

    function loop(curTotal, curIndex) {
      if (curTotal <= 0) return false;

      const pageCount = Math.min(curTotal, size);

      window.requestAnimationFrame(() => {
        const fragment = document.createDocumentFragment();
         for (let i = 0; i < pageCount; i++) {
          const li = document.createElement('li');
          li.innerHTML = `${curIndex + i}: ${~~(Math.random() * total)}`;
          fragment.appendChild(li);
        };
        container.appendChild(fragment);
        loop(curTotal - pageCount, curIndex + pageCount);
      })

    }

    loop(total, index);
  </script>
</body>

虚拟列表

其实是按需显示的一种实现方式，即只对可见区域进行渲染，对不可见区域的数据不渲染或部分渲染的技术，从而达到极高的渲染性能。

思路

  1. 将数据分为以下几个部分：

  • 真实列表长度

  • 偏移位置

  • 可视区域

  • 预渲染区域

实际操作

  • 获取数据条数，创建列表的进度条

  • 计算可视区域高度

  • 请求可视区域数据与预渲染区域（大概是一个可视区域）的数据

  • 渲染可视区域和预渲染区域

  • 监听滚动条，计算偏移位置

  • 根据偏移位置和可视区域，计算需要请求的可视区域和预渲染区域数据的区间范围

  • 请求数据，动态渲染列表

Last Updated:
Contributors: kk