501.二叉搜索树中的众数

链接：501.二叉搜索树中的众数
难度：Easy
标签：树、深度优先搜索、二叉搜索树、二叉树
简介：给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

题解 1 - typescript

• 编辑时间：2020-09-24
• 执行用时：88ms
• 内存消耗：44.1MB
• 编程语言：typescript
• 解法介绍：[参考链接](https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/solution/er-cha-sou-suo-shu-zhong-de-zhong-shu-by-leetcode-/)。

function findMode(root: TreeNode | null): number[] {
  let base = 0;
  let count = 0;
  let maxCount = 0;
  let answer: number[] = [];
  const update = (x: number) => {
    if (x === base) count++;
    else {
      count = 1;
      base = x;
    }
    if (count === maxCount) answer.push(base);
    if (count > maxCount) {
      maxCount = count;
      answer = [base];
    }
  };
  let cur = root,
    pre = null;
  while (cur !== null) {
    if (cur.left === null) {
      update(cur.val);
      cur = cur.right;
      continue;
    }
    pre = cur.left;
    while (pre.right !== null && pre.right !== cur) pre = pre.right;
    if (pre.right === null) {
      pre.right = cur;
      cur = cur.left;
    } else {
      pre.right = null;
      update(cur.val);
      cur = cur.right;
    }
  }
  return answer;
}

题解 2 - typescript

• 编辑时间：2021-08-07
• 执行用时：88ms
• 内存消耗：47.1MB
• 编程语言：typescript
• 解法介绍：中序遍历。

function findMode(root: TreeNode | null): number[] {
  if (root === null) return [];
  const map = new Map<number, number>();
  inorder(root);
  return [...map.entries()]
    .sort(([, v1], [, v2]) => v2 - v1)
    .filter(([, v], _, list) => v === list[0][1])
    .map(([k]) => k);
  function inorder(node: TreeNode | null): void {
    if (node === null) return;
    inorder(node.left);
    map.set(node.val, 1 + (map.get(node.val) ?? 0));
    inorder(node.right);
  }
}

题解 3 - typescript

• 编辑时间：2020-09-24
• 执行用时：120ms
• 内存消耗：47.2MB
• 编程语言：typescript
• 解法介绍：中序遍历。

function findMode(root: TreeNode | null): number[] {
  const cache: Record<number, number> = {};
  const setCache = (val: number) => {
    if (!cache[val]) cache[val] = 0;
    cache[val] += 1;
  };
  const inorder = (root: TreeNode | null) => {
    if (root === null) return;
    inorder(root.left);
    setCache(root.val);
    inorder(root.right);
  };
  inorder(root);
  return Object.entries(cache)
    .sort(([, c1], [, c2]) => c2 - c1)
    .filter(([, c], _, arr) => c === arr[0][1])
    .map(([val]) => parseInt(val));
}