LeetCode 算法笔记 Part2

本文主要记录了博主的 Leetcode 算法刷题记录，方便以后查询复习。

链表

相交链表

哈希表存储遍历的节点，然后进行操作。第二种方法技巧性比较强，利用路径长度相同会回到相交的点的做法来求解。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
const getIntersectionNode = (headA, headB) => {
  const set = new Set();
  while (headA) {
    set.add(headA);
    headA = headA.next;
  }
  while (headB) {
    if (set.has(headB)) {
      return headB;
    } else {
      headB = headB.next;
    }
  }
  return null;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
const getIntersectionNode = (headA, headB) => {
  if (!headA || !headB) {
    return null;
  }
  let p1 = headA,
    p2 = headB;
  while (p1 !== p2) {
    p1 = p1 ? p1.next : headB;
    p2 = p2 ? p2.next : headA;
  }
  return p1;
};

// 测试用例，写的满头大汗，还挺多坑的
class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

const p1 = new ListNode();
const p2 = new ListNode();
let temp = p1;
for (let i = 0; i < 5; i++) {
  temp.next = new ListNode(i);
  temp = temp.next;
}
temp = p2;
for (let i = 0; i < 2; i++) {
  temp.next = new ListNode(i + 10);
  temp = temp.next;
}

let temp0 = p1;
for (let i = 0; i < 3; i++) {
  temp0 = temp0.next;
}
temp.next = temp0;

console.dir(p1, { depth: null });
console.dir(p2, { depth: null });
console.log(getIntersectionNode(p1.next, p2.next));

反转链表

LeetCode 原题链接：206. 反转链表

循环和递归，递归比较难以理解，参考意义不是很大。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const reverseList = (head) => {
  const newHead = new ListNode();
  while (head) {
    const nextEl = head.next;
    head.next = newHead.next;
    newHead.next = head;
    head = nextEl;
  }
  return newHead.next;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const reverseList = (head) => {
  if (!head || !head.next) {
    return head;
  }
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
};

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

const p1 = new ListNode();
let temp = p1;

for (let i = 0; i < 5; i++) {
  temp.next = new ListNode(i);
  temp = temp.next;
}

console.dir(reverseList(p1.next), { depth: null });

回文链表

LeetCode 原题链接：234. 回文链表

将值放在数组中然后进行判断

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
const isPalindrome = (head) => {
  const valArr = [];
  while (head) {
    valArr.push(head.val);
    head = head.next;
  }
  let i = 0,
    j = valArr.length - 1;
  while (i < j) {
    if (valArr[i++] !== valArr[j--]) {
      return false;
    }
  }
  return true;
};

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

const p1 = new ListNode();
let temp = p1;

for (let i = 0; i < 5; i++) {
  temp.next = new ListNode(Math.abs(i - 2));
  temp = temp.next;
}

console.dir(isPalindrome(p1.next), { depth: null });

环形链表

LeetCode 原题链接：141. 环形链表

哈希表与快慢指针，无需多言。🥰

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
const hasCycle = (head) => {
  if (!head) {
    return false;
  }
  const set = new WeakSet();
  let slow = head,
    fast = head.next;
  while (fast) {
    set.add(slow);
    if (set.has(fast)) {
      return true;
    }
    slow = slow.next;
    fast = fast.next?.next;
  }
  return false;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
const hasCycle = (head) => {
  if (!head) {
    return false;
  }
  let slow = head,
    fast = head.next;
  while (fast) {
    slow = slow.next;
    fast = fast.next?.next;
    if (slow === fast) {
      return true;
    }
  }
  return false;
};

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

const p1 = new ListNode();
let temp = p1;
for (let i = 0; i < 5; i++) {
  temp.next = new ListNode(i);
  temp = temp.next;
}
temp.next = p1.next;

console.dir(hasCycle(p1.next), { depth: null });

环形链表 Ⅱ

LeetCode 原题链接：142. 环形链表 Ⅱ

哈希表与快慢指针求解，第二种方法技巧性比较强，参考性不是很高。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const detectCycle = (head) => {
  const set = new WeakSet();
  let p = head;
  while (p) {
    if (set.has(p)) {
      return p;
    }
    set.add(p);
    p = p.next;
  }
  return null;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const detectCycle = (head) => {
  if (head === null) {
    return null;
  }
  let slow = head,
    fast = head;
  while (fast !== null) {
    slow = slow.next;
    if (fast.next !== null) {
      fast = fast.next.next;
    } else {
      return null;
    }
    if (fast === slow) {
      let ptr = head;
      while (ptr !== slow) {
        ptr = ptr.next;
        slow = slow.next;
      }
      return ptr;
    }
  }
  return null;
};

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

const p1 = new ListNode();
let temp = p1;
for (let i = 0; i < 5; i++) {
  temp.next = new ListNode(i);
  temp = temp.next;
}
temp.next = p1.next;

const p2 = new ListNode();
temp = p2;
for (let i = 0; i < 5; i++) {
  temp.next = new ListNode(i + 10);
  temp = temp.next;
}
temp.next = p1.next;

console.dir(p2.next, { depth: null });
console.dir(detectCycle(p2.next), { depth: null });

合并两个有序链表

LeetCode 原题链接：21. 合并两个有序链表

有递归和循环两种写法。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
const mergeTwoLists = (list1, list2) => {
  if (!list1) {
    return list2;
  }
  if (!list2) {
    return list1;
  }
  if (list1.val < list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
const mergeTwoLists = (list1, list2) => {
  const dummy = new ListNode();
  let temp = dummy;
  while (list1 && list2) {
    if (list1.val < list2.val) {
      temp.next = list1;
      list1 = list1.next;
    } else {
      temp.next = list2;
      list2 = list2.next;
    }
    temp = temp.next;
  }
  temp.next = list1 || list2;
  return dummy.next;
};

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

const p1 = new ListNode();
let temp = p1;
for (let i = 0; i < 5; i++) {
  temp.next = new ListNode(i * 2);
  temp = temp.next;
}

const p2 = new ListNode();
temp = p2;
for (let i = 0; i < 5; i++) {
  temp.next = new ListNode(i * 2 + 1);
  temp = temp.next;
}

console.dir(p1.next, { depth: null });
console.dir(p2.next, { depth: null });
console.dir(mergeTwoLists(p1.next, p2.next), { depth: null });

两数相加

LeetCode 原题链接：2. 两数相加

注意进位的处理与归零，其他的都比较简单，思路正确照着写就行。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const addTwoNumbers = (l1, l2) => {
  let head = null,
    tail = null;
  let carry = 0;
  while (l1 || l2 || carry) {
    const n1 = l1 ? l1.val : 0;
    const n2 = l2 ? l2.val : 0;
    const sum = n1 + n2 + carry;
    if (!head) {
      head = tail = new ListNode(sum % 10);
    } else {
      tail.next = new ListNode(sum % 10);
      tail = tail.next;
    }
    carry = Math.floor(sum / 10);
    if (l1) {
      l1 = l1.next;
    }
    if (l2) {
      l2 = l2.next;
    }
  }
  return head;
};

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

const p1 = new ListNode();
let temp = p1;
for (let i = 0; i < 5; i++) {
  temp.next = new ListNode(i * 2);
  temp = temp.next;
}

const p2 = new ListNode();
temp = p2;
for (let i = 0; i < 5; i++) {
  temp.next = new ListNode(i * 2 + 1);
  temp = temp.next;
}

console.dir(p1.next, { depth: null });
console.dir(p2.next, { depth: null });
console.dir(addTwoNumbers(p1.next, p2.next), { depth: null });

删除链表的倒数第 N 个节点

LeetCode 原题链接：19. 删除链表的倒数第 N 个结点

采用计算链表长度或者双指针进行求解

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
const removeNthFromEnd = (head, n) => {
  let length = 0,
    temp = head;
  const newHead = new ListNode(0, head);
  while (temp) {
    length++;
    temp = temp.next;
  }
  temp = newHead;
  for (let i = 0; i < length - n; i++) {
    temp = temp.next;
  }
  temp.next = temp.next.next;
  return newHead.next;
};

class ListNode {
  constructor(val, next) {
    this.val = val;
    this.next = next;
  }
}

const p1 = new ListNode();
let temp = p1;
for (let i = 0; i < 5; i++) {
  temp.next = new ListNode(i);
  temp = temp.next;
}

console.dir(p1.next, { depth: null });
console.dir(removeNthFromEnd(p1.next, 2), { depth: null });

两两交换链表中的节点

LeetCode 原题链接：24. 两两交换链表中的节点

注意指针需要用temp.next.next，便于直接删除。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const swapPairs = (head) => {
  const newHead = new ListNode(0, head);
  let temp = newHead;
  while (temp.next?.next) {
    const firstNode = temp.next;
    const SecondNode = temp.next.next;
    const next = SecondNode.next;
    temp.next = SecondNode;
    SecondNode.next = firstNode;
    firstNode.next = next;
    temp = firstNode;
  }
  return newHead.next;
};

class ListNode {
  constructor(val, next) {
    this.val = val;
    this.next = next;
  }
}

const p1 = new ListNode();
let temp = p1;
for (let i = 0; i < 5; i++) {
  temp.next = new ListNode(i);
  temp = temp.next;
}

console.dir(p1.next, { depth: null });
console.dir(swapPairs(p1.next), { depth: null });

k 个一组翻转链表

LeetCode 原题链接：25. k 个一组翻转链表

该题思路比较简单，但处理情况比较繁琐，十分考量面试者的代码设计能力，推荐将可以翻转的判断与翻转函数书写，同时需要注意翻转后的链表需要连接回原来的链表，所以需要保留上一链表的节点，所以翻转的时候推荐使用temp.next进行翻转。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
const reverseKGroup = (head, k) => {
  const canReverse = (node) => {
    let count = 0;
    while (node) {
      count++;
      node = node.next;
      if (count === k) {
        return true;
      }
    }
    return false;
  };
  const reverse = (node) => {
    const newHead = new ListNode();
    const tail = node;
    for (let i = 0; i < k; i++) {
      const next = node.next;
      node.next = newHead.next;
      newHead.next = node;
      node = next;
    }
    tail.next = node;
    return newHead.next;
  };
  const newHead = new ListNode(0, head);
  let temp = newHead;
  while (canReverse(temp.next)) {
    const tail = temp.next;
    temp.next = reverse(temp.next);
    temp = tail;
  }
  return newHead.next;
};

class ListNode {
  constructor(val, next) {
    this.val = val;
    this.next = next;
  }
}

const p1 = new ListNode();
let temp = p1;
for (let i = 0; i < 5; i++) {
  temp.next = new ListNode(i);
  temp = temp.next;
}

console.dir(p1.next, { depth: null });
console.dir(reverseKGroup(p1.next, 3), { depth: null });

随机链表的复制

LeetCode 原题链接：138. 随机链表的复制

采取哈希表存储原链表与复制之后链表之间节点的对应关系，从而实现复制功能，还可以通过递归实现，但基本思路大致相同

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
const copyRandomList = (head, map = new WeakMap()) => {
  if (!head) {
    return head;
  }
  if (!map.has(head)) {
    map.set(head, new Node(head.val));
    Object.assign(map.get(head), {
      next: copyRandomList(head.next, map),
      random: copyRandomList(head.random, map),
    });
  }
  return map.get(head);
};

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
const copyRandomList = (head) => {
  const newHead = new Node();
  let temp = newHead,
    temp0 = head;
  const map = new WeakMap();
  while (temp0) {
    temp.next = new Node(temp0.val);
    map.set(temp0, temp.next);
    temp0 = temp0.next;
    temp = temp.next;
  }
  temp = newHead.next;
  temp0 = head;
  while (temp0) {
    const random = temp0.random;
    if (random) {
      temp.random = map.get(random);
    } else {
      temp.random = random;
    }
    temp = temp.next;
    temp0 = temp0.next;
  }
  return newHead.next;
};

排序链表

LeetCode 原题链接：148. 排序链表

使用归并排序的思路，求解，左闭右开，同时注意fast指针需要严格遵守fast !== tail的规则来使用。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const sortList = (head) => mergeSort(head, null);

const mergeSort = (head, tail) => {
  if (!head) {
    return null;
  }

  if (head.next === tail) {
    head.next = null;
    return head;
  }

  let slow = head,
    fast = head;
  while (fast !== tail) {
    slow = slow.next;
    fast = fast.next;
    if (fast !== tail) {
      fast = fast.next;
    }
  }
  return mergeTwoLists(mergeSort(head, slow), mergeSort(slow, tail));
};

const mergeTwoLists = (p1, p2) => {
  const dummy = new ListNode();
  let temp = dummy;
  while (p1 && p2) {
    if (p1.val < p2.val) {
      temp.next = p1;
      p1 = p1.next;
    } else {
      temp.next = p2;
      p2 = p2.next;
    }
    temp = temp.next;
  }
  temp.next = p1 || p2;
  return dummy.next;
};

class ListNode {
  constructor(val, next) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

const p1 = new ListNode();
let temp = p1;
for (let i = 0; i < 5; i++) {
  temp.next = new ListNode(Math.floor(Math.random() * 5));
  temp = temp.next;
}
console.dir(p1.next, { depth: null });
console.dir(mergeSort(p1.next, null), { depth: null });

合并 k 个升序链表

LeetCode 原题链接：23. 合并 k 个升序链表

分治与归并排序，掌握思路就比较简单。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
const mergeKLists = (lists) => {
  if (!lists || lists.length === 0) {
    return null;
  }
  if (lists.length === 1) {
    return lists[0];
  }
  if (lists.length === 2) {
    return merge(lists[0], lists[1]);
  }
  const mid = Math.floor(lists.length / 2);
  return merge(mergeKLists(lists.slice(0, mid)), mergeKLists(lists.slice(mid)));
};

const merge = (l1, l2) => {
  if (!l1) {
    return l2;
  }
  if (!l2) {
    return l1;
  }
  if (l1.val < l2.val) {
    l1.next = merge(l1.next, l2);
    return l1;
  } else {
    l2.next = merge(l1, l2.next);
    return l2;
  }
};

LRU 算法

LeetCode 原题链接：146. LRU 缓存

双向链表加上哈希表解决，算法不难，重点是了解其基本思想，注意过量操作需要删除节点。

class Node {
  constructor(key, val) {
    this.key = key;
    this.val = val;
    this.pre = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(size) {
    this.size = size;
    this.dummy = new Node();
    this.dummy.next = this.dummy;
    this.dummy.pre = this.dummy;
    this.map = new Map();
  }

  addFront(el) {
    el.next = this.dummy.next;
    this.dummy.next = el;
    el.pre = this.dummy;
    el.next.pre = el;
  }

  delete(el) {
    el.pre.next = el.next;
    el.next.pre = el.pre;
  }

  put(key, val) {
    if (this.map.has(key)) {
      const el = this.map.get(key);
      el.val = val;
      this.delete(el);
      this.addFront(el);
    } else {
      const el = new Node(key, val);
      this.map.set(key, el);
      this.addFront(el);
      if (this.map.size > this.size) {
        const el = this.dummy.pre;
        this.map.delete(el.key);
        this.delete(el);
      }
    }
  }

  get(key) {
    if (!this.map.has(key)) {
      return -1;
    } else {
      const el = this.map.get(key);
      this.delete(el);
      this.addFront(el);
      return el.val;
    }
  }
}

二叉树

二叉树的前序遍历

LeetCode 原题链接：144. 二叉树的前序遍历

可采用递归和迭代的两种方式，详细理解一下前序遍历迭代的套路。

维护一个结果res与栈stack。
采用while循环循环压入栈，判断条件为root || stack.length。
与中序遍历的区别在于在内部while循环中需要推入res数组，而不是在外部推入。
注意在循环向左压入数字，栈需要更新root，而不是新建一个变量。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const preorderTraversal = (root) => {
  const res = [];
  const dfs = (root) => {
    if (!root) {
      return;
    }
    res.push(root.val);
    dfs(root.left);
    dfs(root.right);
  };
  dfs(root);
  return res;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const preorderTraversal = (root) => {
  const stack = [],
    res = [];
  while (root || stack.length) {
    while (root) {
      res.push(root.val);
      stack.push(root.right);
      root = root.left;
    }
    root = stack.pop();
  }
  return res;
};

二叉树的中序遍历

LeetCode 原题链接：94. 二叉树的中序遍历

可采用递归和迭代的两种方式，详细理解一下中序遍历迭代的套路。

维护一个结果res与栈stack。
采用while循环循环压入栈，判断条件为root || stack.length。
注意在循环向左压入数字，栈需要更新root，而不是新建一个变量。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const inorderTraversal = (root) => {
  const res = [];
  const step = (root) => {
    if (!root) {
      return null;
    }
    step(root.left);
    res.push(root.val);
    step(root.right);
  };
  step(root);
  return res;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const inorderTraversal = (root) => {
  const res = [];
  const stack = [];
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    res.push(root.val);
    root = root.right;
  }
  return res;
};

二叉树的后序遍历

LeetCode 原题链接：145. 二叉树的后序遍历

可采用递归和迭代的两种方式，详细理解一下后序遍历迭代的套路。

维护一个结果res与栈stack。
采用while循环循环压入栈，判断条件为root || stack.length。
注意在循环向左压入数字，栈需要更新root，而不是新建一个变量。
注意与中序遍历不同的是需要将父节点推入stack同时在“触底”的时候记录right变量，防止再一次回溯。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const postorderTraversal = (root) => {
  const res = [];
  const dfs = (root) => {
    if (!root) {
      return;
    }
    dfs(root.left);
    dfs(root.right);
    res.push(root.val);
  };
  dfs(root);
  return res;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const postorderTraversal = (root) => {
  const res = [],
    stack = [];
  let prev = null;
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    if (root.right === null || root.right === prev) {
      res.push(root.val);
      prev = root;
      root = null;
    } else {
      stack.push(root);
      root = root.right;
    }
  }
  return res;
};

二叉树的最大深度

LeetCode 原题链接：104. 二叉树的最大深度

采取递归的思路求解，推荐使用回溯算法，即每个节点从叶子节点开始回溯，每次都返回当前节点左右子节点的最大深度加一，最后返回根节点的最大深度。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
const maxDepth = (root) => {
  if (!root) {
    return 0;
  }
  const left = maxDepth(root.left);
  const right = maxDepth(root.right);
  return Math.max(left, right) + 1;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
const maxDepth = (root) => {
  let max = 0;
  const step = (root, depth = 0) => {
    if (!root) {
      max = Math.max(max, depth);
      return;
    }
    step(root.left, depth + 1);
    step(root.right, depth + 1);
  };
  step(root);
  return max;
};

翻转二叉树

LeetCode 原题链接：226. 翻转二叉树

也是同样的回溯思想，叶子节点开始反转，一直反转到根节点，核心思路为先递归到叶子节点然后一步步返回。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
const invertTree = (root) => {
  if (!root) {
    return root;
  }
  const left = invertTree(root.left);
  const right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
};

对称二叉树

LeetCode 原题链接：101. 对称二叉树

初看这个题目或许比较复杂，但简而言之还是按照深度一层层比较，掌握技巧后就比较简单，注意的是判断条件和递归和迭代的实现思路的细微区别。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const isSymmetric = (root) => {
  const step = (p, q) => {
    if (!p && !q) {
      return true;
    }
    if (!p || !q) {
      return false;
    }
    return p.val === q.val && step(p.left, q.right) && step(p.right, q.left);
  };
  return step(root.left, root.right);
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const isSymmetric = (root) => {
  const queue = [root.left, root.right];
  while (queue.length) {
    const p = queue.shift();
    const q = queue.shift();

    if (!p && !q) {
      continue;
    }
    if (!p || !q || p.val !== q.val) {
      return false;
    }

    queue.push(p.left, q.right, p.right, q.left);
  }
  return true;
};

二叉树的直径

LeetCode 原题链接：543. 二叉树的直径

由二叉树的最大深度稍加改进而来，还是一样，先递归到子节点，然后回溯返回。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
const diameterOfBinaryTree = (root) => {
  let maxD = 0;
  const dfs = (root) => {
    if (!root) {
      return 0;
    }
    const left = dfs(root.left);
    const right = dfs(root.right);
    maxD = Math.max(maxD, left + right);
    return Math.max(left, right) + 1;
  };
  dfs(root);
  return maxD;
};

二叉树的层序遍历

LeetCode 原题链接：102. 二叉树的层序遍历

层序遍历属于广度优先遍历，与深度优先遍历不同，广度优先遍历一般使用队列与循环完成。不需要二维数组，每次遍历都清空queue。
这个算法有两个需要注意的点

只有值不为空的节点才能推入下一次需要遍历的队列。
注意当下一次需要遍历的队列为空的时候，不能推入，防止死循环。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
const levelOrder = (root) => {
  if (!root) {
    return [];
  }

  const queue = [root];
  const res = [];

  while (queue.length) {
    const arr = [];
    const resArr = [];
    while (queue.length) {
      const node = queue.shift();
      resArr.push(node.val);
      if (node.left) {
        arr.push(node.left);
      }
      if (node.right) {
        arr.push(node.right);
      }
    }
    queue.push(...arr);
    res.push(resArr);
  }
  return res;
};

将有序数组转化为二叉搜索树

LeetCode 原题链接：108. 将有序数组转换为二叉搜索树

查看二叉搜索树的详细解释

当然可以。二叉搜索树（Binary Search Tree，简称 BST），也称为二叉查找树或二叉排序树，是一种特殊的二叉树。它具有以下性质：

有序性：对于树中的任意一个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。这意味着所有的元素能够通过比较操作被明确地排序。
递归性质：BST 的左子树和右子树也都是二叉搜索树。这意味着 BST 的定义是递归的，我们可以递归地在子树中进行查找和其他操作。
无重复值：在 BST 中，每个元素必须是唯一的，因为树的定义不允许含有相同值的节点。

二叉搜索树的主要优势在于，它结合了链表和数组的优点：链表的快速插入和删除操作，以及数组的快速查找性能。在平均情况下，查找、插入和删除操作的时间复杂度都是 $O(log n)$ ，其中 $n$ 是树中节点的数量。然而，在最坏的情况下，如果树变得不平衡，这些操作的时间复杂度可能会退化到 $O(n)$ 。

二叉搜索树在计算机科学中应用广泛，特别是在那些需要频繁查找、插入和删除数据的场景中，如数据库和文件系统。

采用二分法将有序数组转化为二叉搜索树，判断条件与二分法基本相同，有着相同的边界处理情况。

left = 0, right = nums.length - 1对应low = 0, high = nums.length - 1
left > right对应low <= high

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
const sortedArrayToBST = (nums) => {
  const step = (left, right) => {
    if (left > right) {
      return null;
    }
    const mid = Math.floor((left + right) / 2);
    const root = new TreeNode(nums[mid]);
    root.left = step(left, mid - 1);
    root.right = step(mid + 1, right);
    return root;
  };
  return step(0, nums.length - 1);
};

验证二叉搜索树

LeetCode 原题链接：98. 验证二叉搜索树

一种方式是采用上下界递归求解，注意左右节点上下界的选取，以及在JS中正负Infinity的使用。另一种方法则是利用二叉搜索树的中序遍历是升序序列来进行判断，可采用递归和循环两种方式，循环方式代码更加优雅一些。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const isValidBST = (root) => {
  const step = (root, lower, upper) => {
    if (!root) {
      return true;
    }
    if (root.val <= lower || root.val >= upper) {
      return false;
    }
    return (
      step(root.left, lower, root.val) && step(root.right, root.val, upper)
    );
  };
  return step(root, -Infinity, Infinity);
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const isValidBST = (root) => {
  const stack = [];
  let pre = -Infinity;
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    if (pre >= root.val) {
      return false;
    }
    pre = root.val;
    root = root.right;
  }
  return true;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const isValidBST = (root) => {
  let pre = -Infinity;
  const dfs = (root) => {
    if (!root) {
      return true;
    }
    const left = dfs(root.left);
    if (pre >= root.val) {
      return false;
    }
    pre = root.val;
    const right = dfs(root.right);
    return left && right;
  };
  return dfs(root);
};

二叉搜索树中第 k 小的元素

LeetCode 原题链接：230. 二叉搜索树中第 k 小的元素

记住中序遍历的套路直接秒。😍

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
const kthSmallest = (root, k) => {
  const stack = [];
  let count = 0;
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    count++;
    if (count === k) {
      return root.val;
    }
    root = root.right;
  }
};

二叉树的右视图

LeetCode 原题链接：199. 二叉树的右视图

和层序遍历大致相同，注意基本思路即可。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const rightSideView = (root) => {
  if (!root) {
    return [];
  }

  const queue = [root];
  const res = [];

  while (queue.length) {
    const arr = [];
    const resArr = [];
    while (queue.length) {
      const node = queue.shift();
      resArr.push(node.val);
      if (node.left) {
        arr.push(node.left);
      }
      if (node.right) {
        arr.push(node.right);
      }
    }
    queue.push(...arr);
    res.push(resArr[resArr.length - 1]);
  }
  return res;
};

二叉树展开为链表

LeetCode 原题链接：144. 二叉树展开为链表

采用前序遍历的操作来解决，其实相当于中序遍历迭代写法的变式。因为在内层while循环中已经开始遍历，所以没有弹出栈后往右遍历的步骤。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
const flatten = (root) => {
  const stack = [];
  const dummy = new TreeNode();
  let temp = dummy;
  while (root || stack.length) {
    while (root) {
      stack.push(root.right);
      temp.right = root;
      temp = temp.right;
      const left = root.left;
      root.left = null;
      root = left;
    }
    root = stack.pop();
  }
  return dummy.right;
};

从前序与中序遍历序列构造二叉树

LeetCode 原题链接：105. 从前序与中序遍历序列构造二叉树

这道题技巧性比较强，主要利用了前序数组与中序数组的相关的性质进行求解。进行根元素和左右元素进行分割。其实本质上也是二分，和将有序数组转化为二叉搜索树相同。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
const buildTree = (preorder, inorder) => {
  const map = new Map();
  for (let i = 0; i < inorder.length; i++) {
    map.set(inorder[i], i);
  }
  const step = (p_start, p_end, i_start, i_end) => {
    if (p_start > p_end) {
      return null;
    }
    const mid = map.get(preorder[p_start]);
    const leftNum = mid - i_start;
    const root = new TreeNode(preorder[p_start]);
    root.left = step(p_start + 1, p_start + leftNum, i_start, mid - 1);
    root.right = step(p_start + leftNum + 1, p_end, mid + 1, i_end);
    return root;
  };
  return step(0, preorder.length - 1, 0, inorder.length - 1);
};

路径总和 III

LeetCode 原题链接：437. 路径总和 III

不考虑时间复杂度直接深度遍历暴力求解，考虑时间复杂度可以使用前缀和的方式进行求解。和和为-k-的子数组思路大致相同。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
const pathSum = (root, targetSum) => {
  const prefix = new Map([[0, 1]]);

  const dfs = (root, curr) => {
    if (!root) {
      return 0;
    }
    curr += root.val;
    let ret = prefix.get(curr - targetSum) || 0;

    prefix.set(curr, (prefix.get(curr) || 0) + 1);
    ret += dfs(root.left, curr);
    ret += dfs(root.right, curr);
    prefix.set(curr, (prefix.get(curr) || 0) - 1);

    return ret;
  };
  return dfs(root, 0);
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
const pathSum = (root, targetSum) => {
  let count = 0;
  const step = (root, sum = 0) => {
    if (!root) {
      return;
    }
    sum += root.val;
    if (targetSum === sum) {
      count++;
    }
    step(root.left, sum);
    step(root.right, sum);
  };
  const preOrder = (root) => {
    if (!root) {
      return;
    }
    step(root);
    preOrder(root.left);
    preOrder(root.right);
  };
  preOrder(root);
  return count;
};

二叉树的最近公共祖先

LeetCode 原题链接：236. 二叉树的最近公共祖先

采用递归的方式求解，注意条件之类的判断，当最深的祖先节点被找到之后，之后的节点不会再满足要求。
主要的判断条件(leftSon && rightSon) || ((p.val === root.val || q.val === root.val) && (leftSon || rightSon))，返回leftSon || rightSon || root.val === p.val || root.val === q.val

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
const lowestCommonAncestor = (root, p, q) => {
  let ans = null;
  const step = (root) => {
    if (!root) {
      return null;
    }
    const leftSon = step(root.left);
    const rightSon = step(root.right);
    if (
      (leftSon && rightSon) ||
      ((root.val === p.val || root.val === q.val) && (leftSon || rightSon))
    ) {
      ans = root;
    }
    return leftSon || rightSon || root.val === p.val || root.val === q.val;
  };
  step(root);
  return ans;
};

124. 二叉树的最大路径和

LeetCode 原题链接：124. 二叉树中的最大路径和

在二叉树的直径与最大深度的代码上改良。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
const maxPathSum = (root) => {
  let max = -Infinity;
  const step = (root) => {
    if (!root) {
      return 0;
    }
    const left = step(root.left);
    const right = step(root.right);
    const sum = Math.max(left, right) + root.val;
    max = Math.max(max, left + right + root.val);
    return sum > 0 ? sum : 0;
  };
  step(root);
  return max;
};

二叉树中和为目标值的路径

LeetCode 原题链接：LCR 153. 二叉树中和为目标值的路径

节省数组空间可采用堆栈弹入或者弹出。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {number[][]}
 */
const pathTarget = (root, target) => {
  const res = [];
  const step = (root, sum, arr) => {
    if (!root) {
      return;
    }
    sum += root.val;
    arr.push(root.val);
    if (!root.left && !root.right && sum === target) {
      res.push([...arr]);
    }
    step(root.left, sum, arr);
    step(root.right, sum, arr);
    arr.pop();
  };
  step(root, 0, []);
  return res;
};