Lstmxx的空间

501. 二叉搜索树中的众数

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

• 结点左子树中所含结点的值小于等于当前结点的值
• 结点右子树中所含结点的值大于等于当前结点的值
• 左子树和右子树都是二叉搜索树

链接

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function findMode(root: TreeNode | null): number[] {
  let res: number[] = []
  let sum = 1
  let pre = null
  let maxSum = sum
  function traverse(root: TreeNode | null) {
    if (root === null) return
    traverse(root.left)
    if (pre === root.val) {
      sum += 1
    } else {
      pre = root.val
      sum = 1
    }
    if (maxSum < sum) {
      res = []
      res.push(root.val)
      maxSum = sum
    } else if (maxSum === sum) {
      res.push(root.val)
    }
    traverse(root.right)
  }
  traverse(root)
  return res
};