1.题目

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按任意顺序返回。

假定 BST 满足如下定义：
结点左子树中所含节点的值小于等于当前节点的值
结点右子树中所含节点的值大于等于当前节点的值
左子树和右子树都是二叉搜索树

示例 1：

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

示例 2：
输入：root = [0]
输出：[0]

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree

2.思路

（1）中序遍历

3.代码实现（Java）

//思路1————中序遍历
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    //res用于保存最终结果，返回时将其转换为数组即可
    ArrayList<Integer> res = new ArrayList<>();
    //preNode表示通过中序遍历到的当前节点的前驱节点
    TreeNode preNode = null;
    //当前元素的重复次数
    int curCnt = 0;
    //全局最长相同序列长度
    int maxCnt = 0;
    
    public int[] findMode(TreeNode root) {
        traverse(root);
        /*
            ArrayList＜Integer＞如何转化为int[]数组？
            Java8新特性:想要转换成int[]类型，就得先转成IntStream
            这里可以通过mapToInt()把Stream<Integer>调用Integer::valueOf来转成IntStream
            然后再用IntStream中默认的toArray()转成int[]
        */
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }
    
    //中序遍历二叉搜索树
    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        //遍历当前根节点的左子树
        traverse(root.left);
        
        //此时可将root节点看成当前遍历到的节点
        if (preNode == null) {
            //初始化前驱节点
            res.add(root.val);
            curCnt = 1;
            maxCnt = 1;
        } else {
            if (root.val == preNode.val) {
                //当前节点的值与前驱节点的值相同
                curCnt++;
                if (curCnt == maxCnt) {
                    //当前节点的值为众数
                    res.add(root.val);
                } else if (curCnt > maxCnt) {
                    //更新众数
                    maxCnt = curCnt;
                    res.clear();
                    res.add(root.val);
                }
            } else {
                //当前节点的值与前驱节点的值不同
                curCnt = 1;
                if (curCnt == maxCnt) {
                    res.add(root.val);
                }
            }
        }
        //更新前驱节点
        preNode = root;
        
        //遍历当前根节点的右子树
        traverse(root.right);
    }
}