17. 二叉搜索树中的众数（501）

一、题目内容 简单

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

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

示例1：

输入：root = [1,null,2,2] 输出：[2]

示例2：

输入：root = [0] 输出：[0]

提示：

• 树中节点的数目在范围 [1, 104] 内
• -105 <= Node.val <= 105

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

二、解题思路

其实二叉搜索树，就当是有序数组，有序数组怎么找众数啊？就从左到右遍历呗，找出重复最多的。
二叉搜索树的中序遍历，就相当于有序数组的遍历。

三、具体代码

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findMode = function (root) {
  let result = []
  let count = 0
  let maxCount = 0
  const stack = []
  let cur = root, pre = null
  while (cur || stack.length) {
    if (cur) {
      stack.push(cur)
      cur = cur.left
    } else {
      cur = stack.pop()
      if (pre) {
        if (pre.val === cur.val) count++
        else count = 1
      } else {
        count = 1
      }
      if (count > maxCount) {
        result = [cur.val]
        maxCount = count
      } else if (count === maxCount) {
        result.push(cur.val)
      }
      pre = cur
      cur = cur.right
    }
  }
  return result
};

四、其他解法

递归法

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findMode = function (root) {
  let result = []
  let pre = null
  let count = 0, maxCount = 0
  const traversal = (node) => {
    if (!node) return
    traversal(node.left)
    if (pre !== null && pre === node.val) {
      count++
    } else {
      count = 1
    }
    pre = node.val
    if (count > maxCount) {
      result = [node.val]
      maxCount = count
    } else if (count === maxCount) {
      result.push(node.val)
    }
    traversal(node.right)
  }
  traversal(root)
  return result
};