力扣501 二叉搜索树中的众数

501. 二叉搜索树中的众数 - 力扣（LeetCode）

二叉搜索树的特点：

中序遍历二叉搜索树是有序序列；

解题思路：

根据中序遍历二叉搜索树是有序序列这一特点，设置频率变量 count ，最大频率变量 maxCount，存储上一个结点值变量 temp 来进行当前结点值出现的频率以及是否需要推入结果数组当中。

如果上一个结点与当前结点值相同，则该结点的频率 + 1；

遍历每一个结点都把当前结点出现的频率与最大频率进行比较，若某一个结点出现的频率大于最大频率了，最大频率就要被替换，由于最大频率被替换了，所以之前结果数组当中记录的值也都要清空并重新推入新的最大频率结点值。

中序遍历非递归方法需要配合栈和指针，栈中最初是空的，树的第一个根结点是没有前一个结点值去进行比较的，所以当临时变量没有值的时候（遍历树的第一个根结点的时候，临时遍历还没有被赋值过）频率设置为 1 ；

遍历的当前结点与上一个结点值比较可能出现的情况：

1.结点为树的第一个根结点，无上一个结点比较：频率变量 count 设置为 1；

2.上一个结点与当前结点值相同：频率变量 count + 1 ；

3.上一个结点与当前结点值不相同： 频率变量 count 重新设置为 1；

最大频率的处理：

因为遍历的结果是有序的，当连续的值相等频率才会增加，每一次遍历都要用当前频率数与最大频率进行比较，若某一个结点出现的频率大于最大频率了，最大频率就要被替换，由于最大频率被替换了，所以之前结果数组当中记录的值也都要清空并重新推入新的最大频率结点值。

注意：

频率  最大频率 要设置为全局变量，一但当前结点与上一个结点值不相同，频率要重置回 1 ，进行该新结点值频率的重新统计。

代码：

// 中序遍历二叉搜索树是有序的，所以可以通过记录遍历时的前后结点值是否相同来记录频率
var findMode = function (root) {
    // 记录结点值出现的频率变量
    let count = 0;
    // 记录当前树中出现频率次数最多为几次的变量
    let maxCount = 0;
    // 中序遍历非递归需要创建的俩个变量
    let stack = [];
    let p = root;
    // 记录上一个结点值
    let temp = undefined;
    // 储存结果
    let res = [];
    while (stack.length || p) {
        while (p) {
            stack.push(p);
            p = p.left;
        }
        let node = stack.pop();
        // 判断当前出栈的结点与上一个结点的值是否相等
        if (temp == undefined) { // 树的第一个结点
            count = 1;
        } else if (temp === node.val) { // 当前结点与上一个结点值相同
            count++;
        } else {
            count = 1; // 与上一个结点值不相同（新值结点）
        }
        // 存储上一个结点的值
        temp = node.val;
        // 如果频率最大值 被刷新了，代表之前存储的结果都符合要求了
        if (count > maxCount) {
            // 清空结果
            res = [];
            // 重新加入新的频率最高的结点值
            res.push(temp);
            // 更新 最高频率 变量
            maxCount = count;
        } else if (maxCount === count) {
            // 如果某一个值从1开始达到了最大频率，推入res
            res.push(temp);
        }
        p = node.right;
    }
    return res;
};