对于 `next.js` 应用，生产环境打包时，可以使用 `preact` 替代 `react` 来优化构建体积。在 `next.config.js` 添加配置：

```js
webpack: (config, { dev, isServer }) => {
    if (!dev && !isServer) {
      Object.assign(config.resolve.alias, {
        'react': 'preact/compat',
        'react-dom/test-utils': 'preact/test-utils',
        'react-dom': 'preact/compat',
      });
    }

    return config;
}
```

1. 使用 `preact`

![preact.jpg](https://wipi.oss-cn-shanghai.aliyuncs.com/2021-10-07/GMCBF3SDVE41GYA0A1BXHT/preact.jpg)

2. 使用 `react`

![react.jpg](https://wipi.oss-cn-shanghai.aliyuncs.com/2021-10-07/GMCBF3SDVE41GYA0A1BXQC/react.jpg)


对于本站，大约可以缩减 `32KB` 的体积。


在生产环境打包时，使用 preact 替代 react 优化构建体积。

使用 preact 优化 next.js 构建体积

本文接下来会一步一步模仿造一个低配版的[`Element 的对话框和弹框组件`](http://element.eleme.io/#/zh-CN/component/message-box)。

## Vue 单文件组件开发

当使用`vue-cli`初始化一个项目的时候，会发现 `src/components` 文件夹下有一个 `HelloWorld.vue` 文件，这便是单文件组件的基本开发模式。

```js
// 注册
Vue.component("my-component", {
  template: "<div>A custom component!</div>",
});

// 创建根实例
new Vue({
  el: "#example",
});
```

接下来，开始写一个 `dialog` 组件。

## Dialog

目标对话框组件的基本样式如图：

![dialog基本样式](https://wipi.oss-cn-shanghai.aliyuncs.com/2021-04-16/dialog.png)

根据目标样式，可以总结出：

1. dialog 组件需要一个 `title` props 来标示弹窗标题
2. dialog 组件需要在按下 `确定` 按钮时 `发射` 出 `确定` 事件（即告诉父组件`确定`了）
3. 同理，dialog 组件需要 `发射` 出 `取消` 事件
4. dialog 组件需要提供一个插槽，便于自定义内容

那么，编码如下:

```html
<template>
  <div class="ta-dialog__wrapper">
    <div class="ta-dialog">
      <div class="ta-dialog__header">
        <span>{{ title }}</span>
        <i class="ios-close-empty" @click="handleCancel()"></i>
      </div>
      <div class="ta-dialog__body">
        <slot></slot>
      </div>
      <div class="ta-dialog__footer">
        <button @click="handleCancel()">取消</button>
        <button @click="handleOk()">确定</button>
      </div>
    </div>
  </div>
</template>

<script>
  export default {
    name: "Dialog",

    props: {
      title: {
        type: String,
        default: "标题",
      },
    },

    methods: {
      handleCancel() {
        this.$emit("cancel");
      },

      handleOk() {
        this.$emit("ok");
      },
    },
  };
</script>
```

这样便完成了`dialog`组件的开发，使用方法如下：

```html
<ta-dialog title="弹窗标题" @ok="handleOk" @cancel="handleCancel">
  <p>我是内容</p>
</ta-dialog>
```

这时候发现一个问题，通过使用 `v-if` 或者 `v-show` 来控制弹窗的展现时，_没有动画！！！_，看上去很生硬。`教练，我想加动画` ,这时候就该 `transition` 组件上场了。使用 `transition` 组件结合 `css`能做出很多效果不错的动画。接下来增强 `dialog` 组件动画，代码如下:

```html
<template>
  <transition name="slide-down">
    <div class="ta-dialog__wrapper" v-if="isShow">
      
    </div>
  </transition>
</template>

<script>
  export default {
    data() {
      return {
        isShow: true,
      };
    },

    methods: {
      handleCancel() {
        this.isShow = false;
        this.$emit("cancel");
      },

      handleOk() {
        this.isShow = true;
        this.$emit("ok");
      },
    },
  };
</script>
```

可以看到 `transition` 组件接收了一个 `name` props，那么怎么编写 `css` 完成动画呢？很简单的方式，写出两个
关键 `class` (css 的 className)样式即可：

```css
.slide-down-enter-active {
  animation: dialog-enter ease 0.3s;
}

.slide-down-leave-active {
  animation: dialog-leave ease 0.5s;
}

@keyframes dialog-enter {
  from {
    opacity: 0;
    transform: translateY(-20px);
  }

  to {
    opacity: 1;
    transform: translateY(0);
  }
}

@keyframes dialog-leave {
  from {
    opacity: 1;
    transform: translateY(0);
  }

  to {
    opacity: 0;
    transform: translateY(-20px);
  }
}
```

就是这么简单就开发出了效果还不错的动效，注意 `transition` 组件的 `name` 为 `slide-down` ,而编写的动画的关键 `className` 为 `slide-down-enter-active` 和 `slide-down-leave-active` 。

## 封装 Dialog 做 MessageBox

Element 的`MessageBox`的使用方法如下:

```js
this.$confirm("此操作将永久删除该文件, 是否继续?", "提示", {
  confirmButtonText: "确定",
  cancelButtonText: "取消",
  type: "warning",
})
  .then(() => {
    this.$message({
      type: "success",
      message: "删除成功!",
    });
  })
  .catch(() => {
    this.$message({
      type: "info",
      message: "已取消删除",
    });
  });
```

看到这段代码，我的感觉就是*好神奇**好神奇**好神奇*（惊叹三连）。仔细看看，这个组件其实就是一个封装好的 `dialog` ,

![Element MessageBox效果](https://wipi.oss-cn-shanghai.aliyuncs.com/2021-04-16/dialog-2.png)

接下来，我也要封装一个这样的组件。首先，整理下思路：

1. Element 的使用方法是 `this.$confirm` ，这不就是挂到 `Vue` 的 `prototype` 上就行了
2. Element 的 `then` 是确定，`catch` 是取消，`promise` 就可以啦

整理好思路，我就开始编码了：

```js
import Vue from "vue";
import MessgaeBox from "./src/index";

const Ctur = Vue.extend(MessgaeBox);
let instance = null;

const callback = (action) => {
  if (action === "confirm") {
    if (instance.showInput) {
      instance.resolve({ value: instance.inputValue, action });
    } else {
      instance.resolve(action);
    }
  } else {
    instance.reject(action);
  }

  instance = null;
};

const showMessageBox = (tip, title, opts) =>
  new Promise((resolve, reject) => {
    const propsData = { tip, title, ...opts };

    instance = new Ctur({ propsData }).$mount();
    instance.reject = reject;
    instance.resolve = resolve;
    instance.callback = callback;

    document.body.appendChild(instance.$el);
  });

const confirm = (tip, title, opts) => showMessageBox(tip, title, opts);

Vue.prototype.$confirm = confirm;
```

至此，可能会疑惑怎么 `callback` 呢，其实我编写了一个封装好的 `dialog` 并将其命名为 `MessageBox` ,
它的代码中，有这样两个方法:

```js
onCancel() {
  this.visible = false
  this.callback && (this.callback.call(this, 'cancel'))
},

onConfirm() {
  this.visible = false
  this.callback && (this.callback.call(this, 'confirm'))
},
```

没错，就是`确定`和`取消`时进行`callback`。我还想说一说`Vue.extend`,代码中引入了`MessageBox`,
我不是直接`new MessageBox`而是借助`new Ctur`，因为这样可以`定义数据(不仅仅是props)`，例如：

```js
instance = new Ctur({ propsData }).$mount();
```

这时候，页面上其实是还没有`MessageBox`的，我们需要执行:

```js
document.body.appendChild(instance.$el);
```

如果你直接这样，你可能会发现 `MessageBox` 打开的时候没有动画，而关闭的时候有动画。解决方法也很简单，
`appendChild`的时候让其仍是不可见，然后使用类这样的代码：

```js
Vue.nextTick(() => (instance.visible = true));
```

这样就有动画了。

## 总结

1. 通过 `transition` 和 `css` 实现不错的动画。其中，`transition` 组件的 `name` 决定了编写 `css` 的两个关键
   类名为 `[name]-enter-active` 和 `[name]-leave-active`
2. 通过 `Vue.extend` 继承一个组件的构造函数（不知道怎么说合适，就先这样说），然后通过这个构造函数，便可以
   实现组件相关属性的自定义（使用场景：js 调用组件）
3. js 调用组件时，为了维持组件的动画效果可以先 `document.body.appendChild` 然后 `Vue.nextTick(() => instance.visible = true)`

<style>
  .slide-down-enter-active {
    animation: dialog-enter ease 0.3s;
  }

  .slide-down-leave-active {
    animation: dialog-leave ease 0.5s;
  }

  @keyframes dialog-enter {
    from {
      opacity: 0;
      transform: translateY(-20px);
    }

    to {
      opacity: 1;
      transform: translateY(0);
    }
  }

  @keyframes dialog-leave {
    from {
      opacity: 1;
      transform: translateY(0);
    }

    to {
      opacity: 0;
      transform: translateY(-20px);
    }
  }
</style>
<style>
  .ta-dialog__wrapper {
    position: fixed;
    left: 0;
    top: 0;
    z-index: 1010;
    width: 100vw;
    height: 100vh;
    background-color: rgba(0, 0, 0, 0.5);
  }
  .ta-dialog {
    position: relative;
    margin: 15vh auto 50px;
    background-color: #fff;
    box-shadow: 0 1px 3px rgba(0, 0, 0, 0.3);
    box-sizing: border-box;
    max-width: 60%;
    min-width: 20%;
  }
  .ta-dialog__header {
    padding: 15px;
    padding-bottom: 10px;
    font-size: 18px;
  }
  .ta-dialog__body {
    padding: 30px 20px;
    color: #606266;
    line-height: 24px;
    font-size: 14px;
    max-height: 60vh;
    overflow: auto;
  }
  .ta-dialog__footer {
    padding: 15px;
    padding-top: 10px;
    text-align: right;
    box-sizing: border-box;
  }
</style>
<script src="https://cdn.bootcdn.net/ajax/libs/vue/2.4.0/vue.min.js" async defer onload="init()"></script>
<script>
  function init() {
    const MessgaeBox = Vue.component("Dialog", {
        template: `
        <transition name="slide-down">
        <div class="ta-dialog__wrapper" v-if="visible">
            <div class="ta-dialog">
            <div class="ta-dialog__header">
                <span>{{ title }}</span>
                <i class="ios-close-empty" @click="handleCancel()"></i>
            </div>
            <div class="ta-dialog__body">
                <slot></slot>
            </div>
            <div class="ta-dialog__footer">
                <button class="ant-btn" @click="handleCancel()">取消</button>
                <button class="ant-btn ant-btn-primary" @click="handleOk()">确定</button>
            </div>
            </div>
        </div>
        </transition>
        `,
        name: "Dialog",
        props: {
        title: {
            type: String,
            default: "标题",
        },
        },
        data() {
        return {
            visible: true,
        };
        },
        methods: {
        handleCancel() {
            this.visible = false;
            this.callback && this.callback.call(this, "cancel");
        },
        handleOk() {
            this.visible = false;
            this.callback && this.callback.call(this, "confirm");
        },
        },
    });
    const Ctur = Vue.extend(MessgaeBox);
    let instance = null;
    const callback = (action) => {
        if (action === "confirm") {
        if (instance.showInput) {
            instance.resolve({ value: instance.inputValue, action });
        } else {
            instance.resolve(action);
        }
        } else {
        instance.reject(action);
        }
        instance = null;
    };
    const showMessageBox = (tip, title, opts) =>
        new Promise((resolve, reject) => {
        const propsData = { tip, title, ...opts };
        instance = new Ctur({ propsData }).$mount();
        instance.reject = reject;
        instance.resolve = resolve;
        instance.callback = callback;
        instance.visible = false;
        document.body.appendChild(instance.$el);
        Vue.nextTick(() => (instance.visible = true));
        });
    const $confirm = (tip, title, opts) => showMessageBox(tip, title, opts);
    Vue.prototype.$confirm = $confirm;
    window.$confirm = $confirm
  }

  function deleteFile() {
    $confirm("此操作将永久删除该文件, 是否继续?", "提示", {
      confirmButtonText: "确定",
      cancelButtonText: "取消",
      type: "warning",
    })
      .then(() => {
        alert("删除成功");
      })
      .catch(() => {
        alert("取消操作");
      });
  }
</script>

## Demo

<button class="ant-btn" onclick="deleteFile()">点我测试</button>

```css
.slide-down-enter-active {
  animation: dialog-enter ease 0.3s;
}

.slide-down-leave-active {
  animation: dialog-leave ease 0.5s;
}

@keyframes dialog-enter {
  from {
    opacity: 0;
    transform: translateY(-20px);
  }

  to {
    opacity: 1;
    transform: translateY(0);
  }
}

@keyframes dialog-leave {
  from {
    opacity: 1;
    transform: translateY(0);
  }

  to {
    opacity: 0;
    transform: translateY(-20px);
  }
}

.ta-dialog__wrapper {
  position: fixed;
  left: 0;
  top: 0;
  z-index: 1010;
  width: 100vw;
  height: 100vh;
  background-color: rgba(0, 0, 0, 0.5);
}
.ta-dialog {
  position: relative;
  margin: 15vh auto 50px;
  background-color: #fff;
  box-shadow: 0 1px 3px rgba(0, 0, 0, 0.3);
  box-sizing: border-box;
  max-width: 60%;
  min-width: 20%;
}
.ta-dialog__header {
  padding: 15px;
  padding-bottom: 10px;
  font-size: 18px;
}
.ta-dialog__body {
  padding: 30px 20px;
  color: #606266;
  line-height: 24px;
  font-size: 14px;
  max-height: 60vh;
  overflow: auto;
}
.ta-dialog__footer {
  padding: 15px;
  padding-top: 10px;
  text-align: right;
  box-sizing: border-box;
}
```

```js
const MessgaeBox = Vue.component("Dialog", {
  template: `
  <transition name="slide-down">
    <div class="ta-dialog__wrapper" v-if="visible">
      <div class="ta-dialog">
        <div class="ta-dialog__header">
          <span>{{ title }}</span>
          <i class="ios-close-empty" @click="handleCancel()"></i>
        </div>
        <div class="ta-dialog__body">
          <slot></slot>
        </div>
        <div class="ta-dialog__footer">
          <button class="ant-btn" @click="handleCancel()">取消</button>
          <button class="ant-btn ant-btn-primary" @click="handleOk()">确定</button>
        </div>
      </div>
    </div>
  </transition>
  `,
  name: "Dialog",
  props: {
    title: {
      type: String,
      default: "标题",
    },
  },
  data() {
    return {
      visible: true,
    };
  },
  methods: {
    handleCancel() {
      this.visible = false;
      this.callback && this.callback.call(this, "cancel");
    },
    handleOk() {
      this.visible = false;
      this.callback && this.callback.call(this, "confirm");
    },
  },
});
const Ctur = Vue.extend(MessgaeBox);
let instance = null;
const callback = (action) => {
  if (action === "confirm") {
    if (instance.showInput) {
      instance.resolve({ value: instance.inputValue, action });
    } else {
      instance.resolve(action);
    }
  } else {
    instance.reject(action);
  }
  instance = null;
};
const showMessageBox = (tip, title, opts) =>
  new Promise((resolve, reject) => {
    const propsData = { tip, title, ...opts };
    instance = new Ctur({ propsData }).$mount();
    instance.reject = reject;
    instance.resolve = resolve;
    instance.callback = callback;
    instance.visible = false;
    document.body.appendChild(instance.$el);
    Vue.nextTick(() => (instance.visible = true));
  });
const $confirm = (tip, title, opts) => showMessageBox(tip, title, opts);
Vue.prototype.$confirm = $confirm;
function deleteFile() {
  $confirm("此操作将永久删除该文件, 是否继续?", "提示", {
    confirmButtonText: "确定",
    cancelButtonText: "取消",
    type: "warning",
  })
    .then(() => {
      alert("删除成功");
    })
    .catch(() => {
      alert("取消操作");
    });
}
```

<button class="ant-btn" onclick="deleteFile()">点我测试</button>

本文接下来会一步一步模仿造一个低配版的 Element 
 的对话框和弹框组件

Vue 组件开发总结

通过地图当前的视口、缩放登记，获取当前可以渲染的数据、被聚合的数据，减少单次渲染量，获取良好性能。

高德地图海量数据展示优化

<h2 id="lru">LRU缓存机制</h2>
<p>运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。<br></p>
<p>获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。<br></p>
<p>写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。</p>
<p><strong>示例:</strong></p>
<pre><code>LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4
</code></pre>
<h3 id="">思路</h3>
<p>维护待删除 key 值的队列，根据使用情况对 key 值进行位置调整。</p>
<pre><code>/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.usedCapacity = 0;
  this.store = Object.create(null);
  this.toDeleteKeys = [];
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (this.store[key]) {
    this.moveKeyToEnd(key);
  }

  return this.store[key] || -1;
};

LRUCache.prototype.moveKeyToEnd = function (key) {
  let arr = this.toDeleteKeys;
  let idx = this.toDeleteKeys.indexOf(key);

  if (idx &lt; 0) {
    return;
  }

  if (idx === arr.length - 1) {
    return;
  }

  arr.splice(idx, 1);
  arr.push(key);
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  if (this.store[key]) {
    this.moveKeyToEnd(key);
    this.store[key] = value;
    return;
  }

  this.toDeleteKeys.push(key);

  if (this.usedCapacity &lt; this.capacity) {
    this.store[key] = value;
    this.usedCapacity += 1;
  } else {
    let deleteKey = this.toDeleteKeys.shift();
    delete this.store[deleteKey];
    this.store[key] = value;
  }
};
</code></pre>
<p>运行结果：</p>
<pre><code>Accepted
18/18 cases passed (256 ms)
Your runtime beats 38.35 % of javascript submissions
Your memory usage beats 100 % of javascript submissions (58.9 MB)
</code></pre>

LeetCode：LRU缓存机制

## 背景

团队使用 TypeScript 进行 React 组件开发。开发组件的同时，需要为组件撰写文档（使用 Markdown 编写文档）。文档中需要对组件的 props 定义进行说明。

![Antd 组件的 API 说明](https://wipi.oss-cn-shanghai.aliyuncs.com/2020-04-26/WX20200426-105830%402x.png)

在开发组件的时候，是编写组件 props 的接口定义。这时候就希望能够偷懒了，直接抽取组件源代码中的接口定义和注释来生成这部分文档。

## 分析

基于上面背景进行分析，可以发现核心需求是抽取组件接口定义和注释形成特定格式的文档。

```ts
import React from "react";

export interface IProps {
  // 文字
  text: string;
  // 点击事件
  onClick: () => void;
}

const Button = ({ text }) => {
  return <button>{text}</button>;
};

export default Button;
```

其实就是抽取 `IProps` 定义然后转换成其他格式文档。

## 思路

在人人都说 `AST` 的今天，我们肯定是要使用 `AST` 来完成。

1. 将源代码转换成 `AST`
2. 遍历 `AST` 抽取 `interface` 定义
3. 继续遍历 `interface` 抽取各个字段定义 `definition`

```shell
code -> ast -> interface -> definitions
```

## 源代码 -> `AST`

站在巨人的肩膀上，使用 `babel` 解析源代码即可。

```js
const parser = require("@babel/parser");

function transformCode2Ast(code) {
  return parser.parse(code, {
    sourceType: "module",
    plugins: [
      "jsx",
      "typescript",
      "asyncGenerators",
      "bigInt",
      "classProperties",
      "classPrivateProperties",
      "classPrivateMethods",
      ["decorators", { decoratorsBeforeExport: false }],
      "doExpressions",
      "dynamicImport",
      "exportDefaultFrom",
      "exportNamespaceFrom",
      "functionBind",
      "functionSent",
      "importMeta",
      "logicalAssignment",
      "nullishCoalescingOperator",
      "numericSeparator",
      "objectRestSpread",
      "optionalCatchBinding",
      "optionalChaining",
      ["pipelineOperator", { proposal: "minimal" }],
      "throwExpressions",
      "topLevelAwait",
      "estree",
    ],
  });
}
```

转换上面的 Button 组件，`AST` 大概长这样：

```js
Node {
  type: 'File',
  start: 0,
  end: 207,
  loc:
   SourceLocation {
     start: Position { line: 1, column: 0 },
     end: Position { line: 16, column: 0 } },
  errors: [],
  program:
   Node {
     type: 'Program',
     start: 0,
     end: 207,
     loc: SourceLocation { start: [Position], end: [Position] },
     sourceType: 'module',
     interpreter: null,
     body: [ [Node], [Node], [Node], [Node] ] },
  comments:
   [ { type: 'CommentLine',
       value: ' 文字',
       start: 57,
       end: 62,
       loc: [SourceLocation] },
     { type: 'CommentLine',
       value: ' 点击事件',
       start: 81,
       end: 88,
       loc: [SourceLocation] } ] }
```

## 遍历 `AST`

同样站在巨人的肩膀上，使用 `ast-types` 对 `ast` 进行遍历。

```ts
const { visit } = require("ast-types");

function findInterface(ast) {
  let ret = Object.create(null);
  let currentInterface = null;

  visit(ast, {
    visitTSInterfaceDeclaration(nodePath) {
      currentInterface = nodePath.value.id.name;
      this.traverse(nodePath);
    },
    visitTSPropertySignature(nodePath) {
      ret[currentInterface] = ret[currentInterface] || [];
      ret[currentInterface].push(nodePath.value);
      return false;
    },
  });
  return ret;
}
```

对 `AST` 遍历抽取 `Interface` 后的结果大概长这样。

```js
Node {
  type: 'TSPropertySignature',
  start: 65,
  end: 78,
  loc: [SourceLocation],
  key: [Node],
  computed: false,
  typeAnnotation: [Node],
  leadingComments: [Array],
  trailingComments: [Array] },
Node {
  type: 'TSPropertySignature',
  start: 91,
  end: 111,
  loc: [SourceLocation],
  key: [Node],
  computed: false,
  typeAnnotation: [Node],
  leadingComments: [Array] } ] }
```

会发现各个定义在 `typeAnnotation` 中，这时候对它进行解析即可。

## 解析 TypeAnnotation

通过分析 `typeAnnotation` 很容易写出。

```js
const get = require("lodash/get");

function parseTSTypeReference(typeName) {
  const type = get(typeName, "type");
  switch (type) {
    case "TSQualifiedName":
      return `${get(typeName, "left.name")}.${get(typeName, "right.name")}`;
    default:
      return `Unknown ReferenceType`;
  }
}

function parseTSFunctionType(parameters, typeAnnotation) {
  const parseTSFunctionParameters = (parameters) => {
    if (!parameters || !parameters.length) {
      return `()`;
    }
    let args = parameters.map((parameter) => {
      return `${get(parameter, "name")}: ${parseTypeAnnotation(
        get(parameter, "typeAnnotation.typeAnnotation")
      )}`;
    });
    return "( " + args.join(", ") + ")";
  };
  const parseTSFunctionReturn = (typeAnnotation) => {
    const type = get(typeAnnotation, "type");
    switch (type) {
      case "TSVoidKeyword":
        return "void";
      case "TSTypeReference":
        return parseTSTypeReference(get(typeAnnotation, "typeName"));
      default:
        return `Unknown FunctionType`;
    }
  };
  return `${parseTSFunctionParameters(parameters)} => ${parseTSFunctionReturn(
    typeAnnotation
  )}`;
}

function parseTSTypeLiteral(members) {
  const ret = parseInterfaceDefinitions(members);
  let args = ret.map((t) => `${t.name}: ${t.type}`);
  return "{ " + args.join(", ") + " }";
}

function parseTypeAnnotation(typeAnnotation) {
  const type = get(typeAnnotation, "type");
  switch (type) {
    case "TSNumberKeyword":
    case "TSStringKeyword":
    case "TSBoleanKeyword":
    case "TSNullKeyword":
    case "TSUndefinedKeyword":
    case "TSSymbolKeyword":
    case "TSAnyKeyword":
      return type.match(/TS(\w+)Keyword/)[1].toLowerCase();
    case "TSUnionType":
      return get(typeAnnotation, "types", [])
        .map((type) => get(type, "literal.value"))
        .join(" | ");
    case "TSFunctionType":
      return parseTSFunctionType(
        get(typeAnnotation, "parameters"),
        get(typeAnnotation, "typeAnnotation.typeAnnotation")
      );
    case "TSTypeReference":
      return parseTSTypeReference(get(typeAnnotation, "typeName"));
    case "TSTypeLiteral":
      return parseTSTypeLiteral(get(typeAnnotation, "members"));
    default:
      return "UnKnowType";
  }
}

function parseInterfaceDefinitions(nodePaths) {
  const parseInterfaceDefinitionsNode = (nodePath) => {
    const name = get(nodePath, "key.name");
    const comments = get(nodePath, "leadingComments.0.value", "")
      .trim()
      .split(/[\r\n]/)
      .map((str) => str.trim().replace(/^\*/g, "").trim())
      .filter(Boolean);
    const typeAnnotation = get(nodePath, "typeAnnotation.typeAnnotation");
    const type = parseTypeAnnotation(typeAnnotation);
    return { name, type, comments };
  };
  return nodePaths.map(parseInterfaceDefinitionsNode);
}
```

至此，可以得到 `Button` 的接口定义。

```js
[
  [
    {
      name: "text",
      type: "string",
      comments: ["文字"],
    },
    {
      name: "onClick",
      type: "() => void",
      comments: ["点击事件"],
    },
  ],
];
```

接下来只要将解析后的结果转成想要的格式即可。

## 测试

```js
function parseTypeScriptComponentInterface(code) {
  let ast = transformCode2Ast(code);
  let interfaces = findInterfaces(ast);
  let definitions = Object.keys(interfaces).reduce((a, c) => {
    a[c] = a[c] || [];
    a[c].push(parseInterfaceDefinitions(interfaces[c]));
    return a;
  }, Object.create(null));
  return definitions;
}

const code = `
import React from 'react';

export interface IProps {
  /**
   * button 
   * 显示文字
   */
  text: string;
  // 点击事件
  onClick: () => void;
  // 属性 3
  props3: (arg: any) => void;
  // 属性 4
  props4: (arg: { name: string, age: number }) => React.Node
}

const Button = ({ text }) => {
  return <button>{text}</button>;
};

export default Button;
`;

let ret = parseTypeScriptComponentInterface(code);
```

输出：

```js
{
  "IProps": [
    [
      {
        "name": "text",
        "type": "string",
        "comments": [
          "button",
          "显示文字"
        ]
      },
      {
        "name": "onClick",
        "type": "() => void",
        "comments": [
          "点击事件"
        ]
      },
      {
        "name": "props3",
        "type": "( arg: any) => void",
        "comments": [
          "属性 3"
        ]
      },
      {
        "name": "props4",
        "type": "( arg: { name: string, age: number }) => React.Node",
        "comments": [
          "属性 4"
        ]
      }
    ]
  ]
}
```

[源代码地址](https://github.com/zhxuc/parse-typescript-component-interface)。


使用 AST 解析 React TypeScript Component 接口定义

# Leetcode

✅ Solutions to LeetCode by JavaScript.

## 简单

- [两数之和](https://github.com/fantasticit/LeetCode/tree/master/Easy/0001.两数之和.js)
- [整数反转](https://github.com/fantasticit/LeetCode/tree/master/Easy/0007.整数反转.js)
- [回文数](https://github.com/fantasticit/LeetCode/tree/master/Easy/0009.回文数.js)
- [有效的括号](https://github.com/fantasticit/LeetCode/tree/master/Easy/0020.有效的括号.js)
- [合并两个有序链表](https://github.com/fantasticit/LeetCode/tree/master/Easy/0021.合并两个有序链表.js)
- [删除排序数组中的重复项](https://github.com/fantasticit/LeetCode/tree/master/Easy/0026.删除排序数组中的重复项.js)
- [移除元素](https://github.com/fantasticit/LeetCode/tree/master/Easy/0027.移除元素.js)
- [实现-str-str](https://github.com/fantasticit/LeetCode/tree/master/Easy/0028.实现-str-str.js)
- [搜索插入位置](https://github.com/fantasticit/LeetCode/tree/master/Easy/0035.搜索插入位置.js)
- [最大子序和](https://github.com/fantasticit/LeetCode/tree/master/Easy/0053.最大子序和.js)
- [最后一个单词的长度](https://github.com/fantasticit/LeetCode/tree/master/Easy/0058.最后一个单词的长度.js)
- [加一](https://github.com/fantasticit/LeetCode/tree/master/Easy/0066.加一.js)
- [二进制求和](https://github.com/fantasticit/LeetCode/tree/master/Easy/0067.二进制求和.js)
- [爬楼梯](https://github.com/fantasticit/LeetCode/tree/master/Easy/0070.爬楼梯.js)
- [删除排序链表中的重复元素](https://github.com/fantasticit/LeetCode/tree/master/Easy/0083.删除排序链表中的重复元素.js)
- [合并两个有序数组](https://github.com/fantasticit/LeetCode/tree/master/Easy/0088.合并两个有序数组.js)
- [相同的树](https://github.com/fantasticit/LeetCode/tree/master/Easy/0100.相同的树.js)
- [对称二叉树](https://github.com/fantasticit/LeetCode/tree/master/Easy/0101.对称二叉树.js)
- [二叉树的最大深度](https://github.com/fantasticit/LeetCode/tree/master/Easy/0104.二叉树的最大深度.js)
- [二叉树的层次遍历-ii](https://github.com/fantasticit/LeetCode/tree/master/Easy/0107.二叉树的层次遍历-ii.js)
- [平衡二叉树](https://github.com/fantasticit/LeetCode/tree/master/Easy/0110.平衡二叉树.js)
- [二叉树的最小深度](https://github.com/fantasticit/LeetCode/tree/master/Easy/0111.二叉树的最小深度.js)
- [只出现一次的数字](https://github.com/fantasticit/LeetCode/tree/master/Easy/0136.只出现一次的数字.js)
- [环形链表](https://github.com/fantasticit/LeetCode/tree/master/Easy/0141.环形链表.js)
- [反转链表](https://github.com/fantasticit/LeetCode/tree/master/Easy/0206.反转链表.js)
- [最小栈](https://github.com/fantasticit/LeetCode/tree/master/Easy/0155.最小栈.js)
- [移除链表元素](https://github.com/fantasticit/LeetCode/tree/master/Easy/0203.移除链表元素.js)
- [存在重复元素](https://github.com/fantasticit/LeetCode/tree/master/Easy/0217.存在重复元素.js)
- [回文链表](https://github.com/fantasticit/LeetCode/tree/master/Easy/0234.回文链表.js)
- [各位相加](https://github.com/fantasticit/LeetCode/tree/master/Easy/0258.各位相加.js)
- [反转字符串](https://github.com/fantasticit/LeetCode/tree/master/Easy/0344.反转字符串.js)
- [找不同](https://github.com/fantasticit/LeetCode/tree/master/Easy/0389.找不同.js)
- [用队列实现栈](https://github.com/fantasticit/LeetCode/tree/master/Easy/0225.用队列实现栈.js)
- [斐波那契数](https://github.com/fantasticit/LeetCode/tree/master/Easy/0509.斐波那契数.js)
- [二分查找](https://github.com/fantasticit/LeetCode/tree/master/Easy/0704.二分查找)
- [反转字符串-ii](https://github.com/fantasticit/LeetCode/tree/master/Easy/0541.反转字符串-ii.js)

## 中等

- [两数相加](https://github.com/fantasticit/LeetCode/tree/master/Medium/0002.两数相加.js)
- [字符串转换整数-atoi](https://github.com/fantasticit/LeetCode/tree/master/Medium/0008.字符串转换整数-atoi.js)
- [盛最多水的容器](https://github.com/fantasticit/LeetCode/tree/master/Medium/0011.盛最多水的容器.js)
- [三数之和](https://github.com/fantasticit/LeetCode/tree/master/Medium/0015.三数之和.js)
- [最接近的三数之和](https://github.com/fantasticit/LeetCode/tree/master/Medium/0016.最接近的三数之和.js)
- [四数之和](https://github.com/fantasticit/LeetCode/tree/master/Medium/0018.四数之和.js)
- [删除链表的倒数第 n 个节点](https://github.com/fantasticit/LeetCode/tree/master/Medium/0019.删除链表的倒数第n个节点.js)
- [括号生成](https://github.com/fantasticit/LeetCode/tree/master/Medium/0022.括号生成.js)
- [两两交换链表中的节点](https://github.com/fantasticit/LeetCode/tree/master/Medium/0024.两两交换链表中的节点.js)
- [两数相除](https://github.com/fantasticit/LeetCode/tree/master/Medium/0029.两数相除.js)
- [在排序数组中查找元素的第一个和最后一个位置](https://github.com/fantasticit/LeetCode/tree/master/Medium/0034.在排序数组中查找元素的第一个和最后一个位置.js)
- [有效的数独](https://github.com/fantasticit/LeetCode/tree/master/Medium/0036.有效的数独.js)
- [字符串相乘](https://github.com/fantasticit/LeetCode/tree/master/Medium/0043.字符串相乘.js)
- [字母异位词分组](https://github.com/fantasticit/LeetCode/tree/master/Medium/0049.字母异位词分组.js)
- [pow-x-n](https://github.com/fantasticit/LeetCode/tree/master/Medium/0050.pow-x-n.js)
- [二叉树的前序遍历](https://github.com/fantasticit/LeetCode/tree/master/Medium/0144.二叉树的前序遍历.js)
- [lru 缓存机制](https://github.com/fantasticit/LeetCode/tree/master/Medium/0146.lru缓存机制.js)
- [最长上升子序列](https://github.com/fantasticit/LeetCode/tree/master/Medium/0300.最长上升子序列)
- [二叉树的中序遍历](https://github.com/fantasticit/LeetCode/tree/master/Medium/0094.二叉树的中序遍历)

## 困难

- [缺失的第一个正数](https://github.com/fantasticit/LeetCode/tree/master/Hard/0041.缺失的第一个正数.js)
- [最小覆盖子串](https://github.com/fantasticit/LeetCode/tree/master/Hard/0076.最小覆盖子串)
- [二叉树的后序遍历](https://github.com/fantasticit/LeetCode/tree/master/Hard/0145.二叉树的后序遍历)

## LICENSE

MIT


LeetCode 刷题

## CSS 自定义属性基本使用方法

自定义属性声明使用两个连词线 `--` 表示（`$color` 是属于Sass的语法，`@color` 是属于Less的语法，为避免冲突，css自定义属性使用 `--` ）。

## 使用 CSS 自定义属性切换主题

通过改变自定义属性值即可达到切换主题的效果。

```
<body>
    <main>
        <h2>标题</h2>
        <p>描述描述</p>
        <button>切换主题</button>
    </main>
</body>
```

```
body {
    --bg: #f4f4f4;
    --text-color: rgba(0, 0, 0, .85);
}

body.dark {
    --bg: #282c35;
    --text-color: rgba(255, 255, 255, .85);
}

* {
    margin: 0;
    padding: 0;
}

main {
    height: 100vh;
    text-align: center;
    background: var(--bg);
    color: var(--text-color);
}

button {
    padding: 4px 8px;
    margin: 20px;
}
```

```
const btn = document.querySelector('button')

btn.onclick = () => {
    if (document.body.classList.contains('dark')) {
        document.body.classList.remove('dark')
    } else {
        document.body.classList.add('dark')
    }
}
```

效果：

<div class="media-wrap image-wrap"><img class="media-wrap image-wrap" src="https://wipi.oss-cn-shanghai.aliyuncs.com/2020-04-06/WX20200406-151334%402x.png" width="50%" style="width:50%"></div>
<div class="media-wrap image-wrap align-left" style="text-align:left"><img class="media-wrap image-wrap align-left" src="https://wipi.oss-cn-shanghai.aliyuncs.com/2020-04-06/WX20200406-151135%402x.png" width="50%" style="width:50%"></div>

## 实现暗黑主题

### 图片处理

为了使图片不至于太过明亮，可以在暗黑主题里降低图片的透明度。

```
@media (prefers-color-scheme: dark) {
    img {
        opacity: .75;
        transition: opacity .5s ease-in-out;
    }
    
    img:hover {
        opacity: 1;
    }
}
```

### 暗黑模式的媒体查询

```
@media (prefers-color-scheme: dark) {
}
```



PS: 兼容性不是很好。



### JavaScript 判断当前系统主题

MacOS、iOS，以及一些较新的安卓手机等都支持了暗黑（深色）模式。可以使用 JS 进行判断。


```
if (window.matchMedia && window.matchMedia('(prefers-color-scheme: dark)').matches) {
    // dark
}
```


## CSS 自定义属性兼容性

<div class="media-wrap image-wrap"><img class="media-wrap image-wrap" src="https://wipi.oss-cn-shanghai.aliyuncs.com/2020-04-06/WX20200406-153648%402x.png"></div>

使用 CSS 变量为网站加上暗黑模式

使用 CSS 自定义属性实现暗黑模式

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中不是连续放置的。每个元素由一个存储元素本身的节点和指向下一个元素的 引用 组成。

```shell
------------------------------------------------------------------------
|                                                                      |
|                node                      node               null     |
|           ---------------          ---------------        --------   |
|  head ->  + item | next +    ->    + item | next +   ->   + null +   |
|           ---------------          ---------------        --------   |
|                                                                      |
------------------------------------------------------------------------
```

```js
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  /**
   * 添加节点
   * @param {*} value
   */
  append(value) {
    return this.insert(value, this.length);
  }

  /**
   * 添加节点到指定位置
   * @param {*} value
   * @param {*} position
   */
  insert(value, position) {
    if (position < 0 || position > this.length) {
      return false;
    }

    let node = new Node(value);

    if (position === 0) {
      node.next = this.head;
      this.head = node;
    } else {
      let prev = null;
      let current = this.head;
      let i = 0;

      while (i++ < position) {
        prev = current;
        current = current.next;
      }

      prev.next = node;
      node.next = current;
    }

    this.length++;
    return true;
  }

  /**
   * 移出指定位置的节点
   * @param {*} position
   */
  removeAt(position) {
    if (position < 0 || position > this.length) {
      return false;
    }

    if (position === 0) {
      this.head = this.head.next;
    } else {
      let prev = null;
      let current = this.head;
      let i = 0;

      while (i++ < position) {
        prev = current;
        current = current.next;
      }

      prev.next = current.next;
    }

    this.length--;
    return true;
  }

  /**
   * 查找给定值所在索引
   * @param {*} value
   */
  indexOf(value) {
    let current = this.head;
    let index = -1;

    while (current) {
      indeex++;
      if (current.value === value) {
        return index;
      } else {
        current = current.next;
      }
    }

    return -1;
  }

  reverse() {
    let prev = null;
    let current = this.head;
    let next = null;

    while (current) {
      next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }

    this.head = prev;
  }

  traverseFromTailToHead() {
    let stack = [];
    let current = this.head;

    while (current) {
      stack.push(current);
      current = current.next;
    }

    while (stack.length) {
      stack.pop();
    }
  }

  getKthNodeFromTailToHead(k) {
    let p1 = this.head;
    let p2 = this.head;
    let i = 0;

    while (i++ < k) {
      p1 = p1.next;
    }

    while (p1) {
      p1 = p1.next;
      p2 = p2.next;
    }

    return p2;
  }
}
```

## 题目

### 1. 输出单链表倒数第 k 个节点


#### 问题描述

题目：输入一个单链表，输出此链表中的倒数第 K 个节点。（去除头结点，节点计数从 1 开始）。

#### 解题思路

倒数第 k 个节点即为整数第 n - k  个节点（n 为链表长度）

- 定义 2 个指针同时执行链表头节点
- 第 1 个指针前进 k 个 节点
- 两个指针同时前进，当第 1 个指针到达链表尾时，第 2 个指针与第一个指针相距 k 个节点，第二个指指向节点即为所求


```js
function findKthTail(linkList, k) {
  let p1 = linkList.head;
  let p2 = linkList.head;
  let i = 0;

  while (i++ < k) {
    p1 = p1.next;
  }

  while (p1) {
    p1 = p1.next;
    p2 = p2.next;
  }

  return p2; 
}
```


### 2. 判断链表是否有环


#### 问题描述

单链表中的环是指链表末尾的节点的 next 指针不为 NULL ，而是指向了链表中的某个节点，导致链表中出现了环形结构。

```shell
0 -> 1 -> 2 -> 3 -> 4
               |    |
               6 <- 5
```

链表中尾节点 `6` 指向了 节点 `3` 而非 `null`，导致出现了环形结构。 


#### 解题思路

- 定义 2 个快慢指针，初始均指向头节点
- 第 1 个指针前进 1 步，第 2 个指针前进 2 步
- 若是无环，2 个指针最后均指向 `null`，但若是有环，2 指针必定在一个节点处相遇，该节点不为 `null`


```js
/**
 * 判断链表是否存在环
 * @param {*} linkList
 */
function isExistLoop(linkList) {
  let p1 = linkList.head;
  let p2 = linkList.head;

  while (p1 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;

    if (p1 === p2) {
      return true;
    }
  }

  return false;
}
```

#### 问题描述

定位环的起点。


#### 解题思路

定义2个快慢指针，第一次先找到 2 个指针在环中的相遇点，然后令 p1 指向 相遇点，p2 指向头节点，同时出发（每次走过的节点相同），当 2 指针指向的节点相同时，p1 即为环的起点。

```js
function getMeetingNode(linkList) {
  let p1 = linkList.head;
  let p2 = linkList.head;

  while (p1 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;

    if (p1 == p2) {
      return p1;
    }
  }

  return null;
}

function getEntryOfLoop(linkList) {
  let meetingNode = linkList.getMeetingNode();

  if (!meetingNode) {
    return null;
  }

  let p1 = meetingNode;
  let p2 = linkList.head;

  while (p1 != p2) {
    p1 = p1.next;
    p2 = p2.next;
  }

  return p1;
}
```

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中不是连续放置的。每个元素由一个存储元素本身的节点和指向下一个元素的 引用 组成。

JavaScript 数据结构：链表

## 冒泡排序

冒泡排序重复遍历数组，依次比较 2 个元素，如这 2 个元素顺序错误，就交换位置。

- 比较相邻的元素，若前者大于后者就交换
- 对每一对相邻的元素执行上一部动作
- 经过前 2 步，最大的元素已经到数组最后一项，对剩下的前 n - 1 项重复前 2 步即可

```js
function bubbleSort(arr) {
  let len = arr.length;

  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}
```

## 选择排序

选择排序时间复杂度 `O(n²)`。

- 在未排序数列中，找到最小元素，存放到起始位置
- 从剩余未排序数列中，找到最小元素，放到已排序数列末尾
- 重复第 2 步知道完成

```js
function selectSort(arr) {
  let len = arr.length
  let minIndex = 0
  
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
  }
  
  return arr
}
```

## 插入排序

插入排序首先构建有序数列，然后在有序数列中从后向前插入未排序元素。

- 将第 1 个元素看作已排序数列，将其后元素看作未排序数列
- 遍历未排序数列，将元素插入到已排序数列中的合适位置

```js
function insertSort(arr) {
  let len = arr.length
  
  for (let i = 1; i < len; i++) {
    let j = i - 1;
    let tmp = arr[i]
    
    while (j >= 0 && arr[j] > tmp) {
      arr[j + 1] = arr[j]
      j--
    }
    
    arr[j + 1] = tmp
  }
  
  return arr
}
```

## 希尔排序

希尔排序是插入排序的更高效改进版。建立于插入排序的 2 点特性：

- 插入排序对几乎已经排列好的数列排序效率高
- 插入排序低效是因为 1 次只能移动 1 位


希尔排序的步骤。

- 选择一个增量序列，t1, t2, ..., tk，其中 ti > tj, tk = 1
- 按增量序列个数 k，对序列进行 k 趟排序
- 当增量因子为 1 时，整个序列进行 1 次排序

```js
function shellSort(arr) {
  let len = arr.length;
  let gap = 1;

  while (gap < len / 3) {
    gap = gap * 3 + 1;
  }

  for (; gap > 0; gap = Math.floor(gap / 3)) {
    for (let i = gap; i < len; i++) {
      let tmp = arr[i];
      let j = i - gap;

      while (j >= 0 && arr[j] > tmp) {
        arr[j + gap] = arr[j];
        j -= gap;
      }

      arr[j + gap] = tmp;
    }
  }

  return arr;
}
```

## 归并排序

归并排序是采用分治法的典型例子。

- 拆分数组为 2 部分
- 比较 2 部分数列
- 重复前 2 步

```js
function mergeSort(arr) {
  let len = arr.length
  
  if (len <= 1) {
    return arr
  }
  
  let middle = len >> 1
  let left = arr.slice(0, middle)
  let right = arr.slice(middle)
  
  const merge = (left, right) => {
    let ret = []
    
    while (left.length && right.length) {
      if (left[0] < right[0]) {
        ret.push(left.shift())
      } else {
        ret.push(right.shift())
      }
    }
    
    while (left.length) {
      ret.push(left.shift())
    }
    
    while (right.length) {
      ret.push(right.shift())
    }
    
    return ret
  }
  
  return merge(mergeSort(left), mergeSort(right))
}
```


## 快速排序

快速排序采用分治法将 1 个数列分成 2 个子数列进行处理。

- 从数列中挑出一个基准值
- 将把基准值小的值，放在前，大的放在后
- 递归地重新排列划分后的 2 个子数列

```js
function quickSort(arr, left, right) {
  if (arr.length <= 1) {
    return arr;
  }

  let pivotIndex = Math.floor(arr.length / 2);
  let pivot = arr.splice(pivotIndex, 1)[0];
  let left = [];
  let right = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return quickSort(left).concat([pivot], quickSort(right));
}
```


JavaScript 排序算法


## 二叉搜索树

二叉树中的节点最多只能有 2 个子节点：左侧子节点 和 右侧子节点。 二叉搜索树是二叉树的一种，但是它只允许在左侧子节点存储比父节点小的值，在右侧子节点存储大于等于父节点的值。


```js
class Node {
  constructor(value) {
    this.left = null;
    this.value = value;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  /**
   * 插入节点
   * @param {} value
   */
  insert(value) {
    const newNode = new Node(value);

    if (!this.root) {
      this.root = newNode;
    } else {
      let root = this.root;
      insertNode(root, newNode);

      function insertNode(node, newNode) {
        if (node.value < newNode.value) {
          if (node.right === null) {
            node.right = newNode;
          } else {
            insertNode(node.right, newNode);
          }
        } else {
          if (node.left === null) {
            node.left = newNode;
          } else {
            insertNode(node.left, newNode);
          }
        }
      }
    }

    return true;
  }

  /**
   * 按值查找节点
   * @param {*} value
   */
  search(value) {
    const _search = (node, value) => {
      if (node === null) {
        return false;
      }

      if (node.value > value) {
        return _search(node.left, value);
      } else if (node.value < value) {
        return _search(node.right, value);
      } else {
        return node;
      }
    };

    return _search(this.root, value);
  }
}
```

## 先序遍历

先序遍历的顺序是：**根 -> 左 -> 右**。

### 递归版

```js
function preTraverse(bsTree) {
  const traverse = (node, queue) => {
    if (!node) {
      return queue;
    } else {
      queue.push(node);
      traverse(node.left, queue);
      traverse(node.right, queue);
    }
  };
  const queue = [];
  traverse(bsTree.root, queue);
  return queue;
}
```

### 循环版


```js
function preTraverse(bsTree) {
  let stack = [];
  let queue = [];
  let node = bsTree.root;

  stack.push(node);

  while (stack.length > 0) {
    let currentNode = stack.pop();
    queue.push(currentNode);

    if (currentNode.right) {
      stack.push(currentNode.right);
    }

    if (currentNode.left) {
      stack.push(currentNode.left);
    }

  }

  return queue;
}
```


## 中序遍历

中序遍历的顺序是：**左 -> 根 -> 右**。

### 递归版

```js
function inorderTraverse(bsTree) {
  const traverse = (node, queue) => {
    if (!node) {
      return;
    }
    traverse(node.left, queue);
    queue.push(node);
    traverse(node.right, queue);
  };
  const queue = [];
  traverse(bsTree.root, queue);
  return queue;
}
```

### 循环版


```js
function inorderTraverse(bsTree) {
  const stack = [];
  const queue = [];
  let currentNode = bsTree.root;

  while (currentNode || stack.length > 0) {
    if (currentNode != null) {
      stack.push(currentNode);
      currentNode = currentNode.left;
    } else {
      currentNode = stack.pop();
      queue.push(currentNode);
      currentNode = currentNode.right;
    }
  }

  return queue;
}
```

循环版的思路：

1. 首先将所有左节点压入栈中
2. 将栈弹出到队列中
3. 当前节点回归到跟节点，依次入列右节点


```js
function inorderTraverse(bsTree) {
  const stack = [];
  const queue = [];
  let currentNode = bsTree.root;

  while (currentNode) {
    currentNode = currentNode.left;
    stack.push(currentNode);
  }

  while (stack.length) {
    queue.push(stack.pop());
  }

  currentNode = bsTree.root;

  while (currentNode) {
    queue.push(currentNode);
    currentNode = currentNode.right;
  }

  return queue;
}
```

## 后序遍历

后序遍历的顺序是：**左 -> 右 -> 根**。

### 递归版

```js
function postorderTraverse(bsTree) {
  const traverse = (node, queue) => {
    if (!node) {
      return;
    }

    traverse(node.left, queue);
    traverse(node.right, queue);
    queue.push(node);
  };
  const queue = [];
  traverse(bsTree.root, queue);
  return queue;
}
```

### 循环版

```js
function postorderTraverse(bsTree) {
  let stack = []
  let queue = []
  let node = bsTree.root
  stack.push(node)
  
  while (stack.length) {
    node = stack.pop()
    if (node.left) {
      stack.push(node.left)
    }
    if (node.right) {
      stack.push(node.right)
    }
    queue.unshift(node)
  }
  
  return queue
}
```

## 题目

### 1. 层级遍历

#### 问题描述

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:

```shell
          11
       /      \
      7       15
     / \     /  \
    3   6   12  16
```
层级遍历结果: 

```js
[
  [11],
  [7, 15],
  [3, 6, 12, 16]
]
```

#### 解题思路

- 建立一个queue
- 先把根节点放进去，这时候找根节点的左右两个子节点
- 去掉根节点，此时queue里的元素就是下一层的所有节点
- 用for循环遍历，将结果存到一个一维向量里
- 遍历完之后再把这个一维向量存到二维向量里
- 以此类推，可以完成层序遍历

```js
function levelTraverse(bsTree) {
  let queue = []
  let ret = []
  let node = bsTree.root
  queue.push(node)
  
  while (queue.length) {
    const count = queue.length
    const subRet = []
    
    while (count > 0) {
      node = queue.pop()
      subRet.push(node)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
    
    ret.push(subRet)
  }
  
  return subRet
}
```


二叉树中的节点最多只能有 2 个子节点：左侧子节点 和 右侧子节点。 二叉搜索树是二叉树的一种，但是它只允许在左侧子节点存储比父节点小的值，在右侧子节点存储大于等于父节点的值。

JavaScript 数据结构：二叉搜索树 


## 0. 什么是 vnode

相信大部分前端同学之前早已无数次听过或了解过 `vnode`（虚拟节点），那么什么是 `vnode`? `vnode` 应该是什么样的？
如果不使用前端框架，我们可能会写出这样的页面：

```html
<html>
  <head>
    <title></title>
  </head>
  <body>
    <div></div>
    <script></script>
  </body>
</html>
```

不难发现，整个文档树的根节点只有一个 `html`，然后嵌套各种子标签，如果使用某种数据结构来表示这棵树，那么它可能是这样。

```javascript
{
  tagName: 'html',
  children: [
    {
      tagName: 'head',
      children: [
        {
          tagName: 'title'
        }
      ]
    },

    {
      tagName: 'body',
      children: [
        {
          tagName: 'div'
        },

        {
          tagName: 'script'
        }
      ]
    }
  ]
}
```

但是实际开发中，整个文档树中`head` 和 `script` 标签基本不会有太大的改动。频繁交互可能改动的应当是 `body` 里面的除 `script` 的部分，所以构建 虚拟节点树 应当是整个 HTML 文档树的一个子树，而这个子树应当保持和 HTML 文档树一致的数据结构。它可能是这样。

```html
<html>
  <head>
    <title></title>
  </head>
  <body>
    <div id="root">
      <div class="header"></div>
      <div class="main"></div>
      <div class="footer"></div>
    </div>
    <script></script>
  </body>
</html>
```

这里应当构建的 虚拟节点树 应当是 `div#root` 这棵子树：

```javascript
{
  tagName: 'div',
  children: [
    {
      tagName: 'div',
    },
    {
      tagName: 'div',
    },
    {
      tagName: 'div',
    },
  ]
}
```

到这里，vnode 的概念应当很清晰了，vnode 是用来表示实际 dom 节点的一种数据结构，其结构大概长这样。

```javascript
{
  tagName: 'div',
  attrs: {
    class: 'header'
  },
  children: []
}
```

一般，我们可能会这样定义 `vnode`。

```javascript
// vnode.js
export const vnode = function vnode() {}
```

## 1. 从 JSX 到 vnode

使用 `React` 会经常写 `JSX`，那么如何将 `JSX` 表示成 `vnode`？这里可以借助 `@babel/plugin-transform-react-jsx` 这个插件来自定义转换函数，
只需要在 `.babelrc` 中配置：

```javascript
{
  "plugins": [
    [
      "@babel/plugin-transform-react-jsx",
      {
        "pragma": "window.h"
      }
    ]
  ]
}

```

然后在 `window` 对象上挂载一个 `h` 函数：

```javascript
// h.js
const flattern = arr => [].concat.apply([], arr)

window.h = function h(tagName, attrs, ...children) {
  const node = new vnode()
  node.tagName = tagName
  node.attrs = attrs || {}
  node.children = flattern(children)

  return node
}
```

测试一下：

![jsx->vnode](https://user-images.githubusercontent.com/26452939/49918605-beacf180-fede-11e8-80f7-541f02519a02.png)

## 2. 渲染 vnode

现在我们已经知道了如何构建 `vnode`，接下来就是将其渲染成真正的 dom 节点并挂载。

```javascript
// 将 vnode 创建为真正的 dom 节点
export function createElement(vnode) {
  if (typeof vnode !== 'object') {
    // 文本节点
    return document.createTextNode(vnode)
  }

  const el = document.createElement(vnode.tagName)
  setAttributes(el, vnode.attrs)
  vnode.children.map(createElement).forEach(el.appendChild.bind(el))
  return el
}

// render.js
export default function render(vnode, parent) {
  parent = typeof parent === 'string' ? document.querySelector(parent) : parent
  return parent.appendChild(createElement(vnode))
}
```

这里的逻辑主要为：

1. 根据 `vnode.tagName` 创建元素
2. 根据 `vnode.attrs` 设置元素的 `attributes`
3. 遍历 `vnode.children` 并将其创建为真正的元素，然后将真实子元素节点 append 到第 1 步创建的元素

## 3. diff vnode

第 2 步已经实现了 `vnode` 到 `dom` 节点的转换与挂载，那么接下来某一个时刻 `dom` 节点发生了变化，如何更新 `dom`树?显然不能无脑卸载整棵树，然后挂载新的树，最好的办法还是找出两棵树之间的差异，然后应用这些差异。

![diff-2-vnode](https://user-images.githubusercontent.com/26452939/49936056-d6e83500-ff0d-11e8-81ff-d1620acb31c4.png)

在写 `diff` 之前，首先要定义好，要 `diff`  什么，明确 `diff` 的返回值。比较上图两个 vnode，可以得出：

1. 更换第 _1、2、3_ 个 `li` 的内容
2. 在 `ul` 下创建两个 `li`，这两个 li 为 *第 4 个*和 *第 5 个*子节点

那么可能得返回值为：

```javascript
{
  "type": "UPDATE",
  "children": [
    {
      "type": "UPDATE",
      "children": [
        {
          "type": "REPLACE",
          "newVNode": 0
        }
      ],
      "attrs": []
    },
    {
      "type": "UPDATE",
      "children": [
        {
          "type": "REPLACE",
          "newVNode": 1
        }
      ],
      "attrs": []
    },
    {
      "type": "UPDATE",
      "children": [
        {
          "type": "REPLACE",
          "newVNode": 2
        }
      ],
      "attrs": []
    },
    {
      "type": "CREATE",
      "newVNode": {
        "tagName": "li",
        "attrs": {},
        "children": [
          3
        ]
      }
    },
    {
      "type": "CREATE",
      "newVNode": {
        "tagName": "li",
        "attrs": {},
        "children": [
          4
        ]
      }
    }
  ],
  "attrs": []
}
```

`diff` 的过程中，要保证节点的父节点正确，并要保证该节点在父节点 的子节点中的索引正确（保证节点内容正确，位置正确）。`diff` 的核心流程：

- case CREATE: 旧节点不存在，则应当新建新节点
- case REMOVE: 新节点不存在，则移出旧节点
- case REPLACE: 只比较新旧节点，不比较其子元素，新旧节点标签名或文本内容不一致，则应当替换旧节点
- case UPDATE: 到这里，新旧节点可能只剩下 attrs 和 子节点未进行 diff，所以直接循环 diffAttrs 和 diffChildren 即可

```javascript
/**
 * diff 新旧节点差异
 * @param {*} oldVNode
 * @param {*} newVNode
 */
export default function diff(oldVNode, newVNode) {
  if (isNull(oldVNode)) {
    return { type: CREATE, newVNode }
  }

  if (isNull(newVNode)) {
    return { type: REMOVE }
  }

  if (isDiffrentVNode(oldVNode, newVNode)) {
    return { type: REPLACE, newVNode }
  }

  if (newVNode.tagName) {
    return {
      type: UPDATE,
      children: diffVNodeChildren(oldVNode, newVNode),
      attrs: diffVNodeAttrs(oldVNode, newVNode)
    }
  }
}
```

## 4. patch 应用更新

知道了两棵树之前的差异，接下来如何应用这些更新？在文章开头部分我们提到 `dom` 节点树应当只有一个根节点，同时 `diff` 算法是保证了虚拟节点的位置和父节点是与 `dom` 树保持一致的，那么 patch 的入口也就很简单了，从 虚拟节点的挂载点开始递归应用更新即可。

```javascript
/**
 * 根据 diff 结果更新 dom 树
 * 这里为什么从 index = 0 开始？
 * 因为我们是使用树去表示整个 dom 树的，传入的 parent 即为 dom 挂载点
 * 从根节点的第一个节点开始应用更新，这是与整个dom树的结构保持一致的
 * @param {*} parent
 * @param {*} patches
 * @param {*} index
 */
export default function patch(parent, patches, index = 0) {
  if (!patches) {
    return
  }

  parent = typeof parent === 'string' ? document.querySelector(parent) : parent
  const el = parent.childNodes[index]

  /* eslint-disable indent */
  switch (patches.type) {
    case CREATE: {
      const { newVNode } = patches
      const newEl = createElement(newVNode)
      parent.appendChild(newEl)
      break
    }

    case REPLACE: {
      const { newVNode } = patches
      const newEl = createElement(newVNode)
      parent.replaceChild(newEl, el)
      break
    }

    case REMOVE: {
      parent.removeChild(el)
      break
    }

    case UPDATE: {
      const { attrs, children } = patches

      patchAttrs(el, attrs)

      for (let i = 0, len = children.length; i < len; i++) {
        patch(el, children[i], i)
      }

      break
    }
  }
}
```

## 总结

至此，`vdom` 的核心 `diff` 与 `patch` 都已基本实现。在测试 demo 中，不难发现 `diff` 其实已经很快了，但是 `patch` 速度会比较慢，所以这里留下了一个待优化的点就是 `patch`。

本文完整代码均在这个[仓库](https://github.com/fantasticit/vdom)。


相信大部分前端同学之前早已无数次听过或了解过 vnode（虚拟节点），那么什么是 vnode? vnode 应该是什么样的？