Day9

算法题

109. 有序链表转换二叉搜索树

给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。

示例 1:

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。
示例 2:

输入: head = []
输出: []

提示:

head 中的节点数在[0, 2 * 104] 范围内
-105 <= Node.val <= 105

 var sortedListToBST = function(head) {
     if (head == null) return null
    // 用快慢指针找到中间节点
    var slow = head
    var fast = head
    var preSlow
    while(fast && fast.next) {
        // 为了左右断开，需要有保存前一个结点
        preSlow = slow
        slow = slow.next
        fast = fast.next.next
    }
    var root = new TreeNode(slow.val)
    if (preSlow != null) {
        preSlow.next = null
        root.left = sortedListToBST(head)
    }
    root.right = sortedListToBST(slow.next)
    return root
};

题解：
https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/shou-hua-tu-jie-san-chong-jie-fa-jie-zhu-shu-zu-ku/

手写题

1. 实现一个Event Emitter ```javascript Node.js中有Event Emitter，Facebook 也曾经有自己的实现 不过已经archive了。

请实现你自己的 Event Emitter

const emitter = new Emitter() 它需要支持事件订阅

const sub1 = emitter.subscribe(‘event1’, callback1) const sub2 = emitter.subscribe(‘event2’, callback2)

// 同一个callback可以重复订阅同一个事件 const sub3 = emitter.subscribe(‘event1’, callback1) emit(eventName, …args) 可以用来触发callback

emitter.emit(‘event1’, 1, 2); // callback1 会被调用两次 subscribe()返回一个含有release()的对象，可以用来取消订阅。

sub1.release() sub3.release() // 现在即使’event1’被触发, // callback1 也不会被调用

```javascript
// please complete the implementation
class EventEmitter {
  constructor() {
    this.eventMap = {}
  }
  subscribe(eventName, callback) {
    if (this.eventMap[eventName] && this.eventMap[eventName].length) {
      this.eventMap[eventName].push(callback)
    } else {
      this.eventMap[eventName] = [callback]
    }
    let len = this.eventMap[eventName].length - 1
    return {
      release: () => {
        this.eventMap[eventName].splice(len, 1)
      }
    }
  }
  emit(eventName, ...args) {
    if (this.eventMap[eventName]) {
      this.eventMap[eventName].forEach((callback) => {
        callback.call(this, ...args)
      })
    }
  }
}