501.二叉查找树中的最小值(javascript)501.FindModeinBinarySearchTree

为您提供具有重复值的二进制搜索树(BST)的根节点 root ，找到并返回 BST 中的所有 模式（即，出现频率最高的元素）。

如果果树中有多个模式，可以按 任意顺序 返回。

假定 BST 满足以下定义：

• 节点左子树中包含的节点值。 小于等于 当前节点的值
• 节点右子树中包含的节点值。 大于等于 当前节点的值
• 左子树和右子树都是二进制搜索树。

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in any order.

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
• Both the left and right subtrees must also be binary search trees.

示例 1：

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

示例 2：

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

提示：

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

解题思路
二叉树中顺序遍历的本质：二叉树的顺序遍历序列是一个非递减的顺序序列。我们可以发现重复的数字必须是连续的

base 对于当前编号
number 与当前编号对应的出现次数
maxNumber 对于出现次数
answer 对于出现的模式数组

首先更新 base 和 count:

• 如果元素和 base 那么等于 number 自增 1；
• 否则将 base 更新为当前编号，number 复位为 1。

然后更新 maxNumber：

• 如果 number=maxNumber，然后是当前号码(base出现的次数等于当前模式的出现次数。 base 加入answer 数组；
• 如果 number>maxNumber，然后是当前号码(base出现的次数大于当前模式的出现次数，因此我们需要 maxNumber 更新为number，清空 answer 数组后将base 加入 answer 数组。

我们可以将此过程写成 update 作用这样，当我们寻找出现最多的数字时，我们可以节省哈希带的空间消耗。

var findMode = function (root) {
    let base = 0, number = 0, maxNumber = 0, answer = []
    var getAnswer = function (value) {
        if (value === base) {
            ++number
        } else {
            number = 1
            base = value
        }
        if (number === maxNumber) {
            answer.push(base)
        } else if (number > maxNumber) {
            maxNumber = number
            answer = [base]
        }
    }
    var dfs = function (root) {
        if (!root) return
        dfs(root.left)
        getAnswer(root.val)
        dfs(root.right)
    };
    dfs(root)
    return answer
};

//中阶遍历的方法。
var dfs = function (root) {
        if (!root) return
        dfs(root.left)
        getAnswer(root.val)
        dfs(root.right)
    };

leetcode： https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/