LeetCode/501. 二叉搜索树中的众数

501. 二叉搜索树中的众数

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

假定 BST 有如下定义：

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

例如：
给定 BST [1,null,2,2],

1
 \
  2
 /
2

返回[2].

提示：如果众数超过1个，不需考虑输出顺序

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

二叉搜索树有一个很重要的特性，就是如果按照中序遍历二叉搜索树，我们会得到一个值依次递增的序列，所以只需要判断当前结点和父结点出现的次数，就可以得到结果数组。具体来说我们中序遍历一棵树，如果当前结点的值和父结点值相等，那我们就给currTime自增，如果当前结点是root结点，那么将currTime初始化为1。如果当前值出现次数比maxTime还大，那么将currTime的值赋给maxTime，并且将结果数组中的值清空，将当前结点的值加入到结果数组中；如果两者相等，即为两个不同的值出现次数相同的情况，我们将它们一并加入到结果数组中。

具体代码如下：

class Solution {
        List<Integer> result = new LinkedList<>();
        int maxTime = 0;
        int currTime = 0;
        TreeNode preNode = null;

        public int[] findMode(TreeNode root) {
            inOrder(root);
            int len = result.size();
            int[] current = new int[len];
          	//将结果数组中的值取出以int[]形式返回
            for (int i = 0; i < len; i++) {
                current[i] = result.get(i);
            }
            return current;
        }

  			//中序遍历树
        void inOrder(TreeNode node) {
            if (node == null) {
                return;
            }
            inOrder(node.left);
            //判断当前出现次数是否为第一次，若是第一次初始化出现次数为1，否则自增加一
            if (preNode != null && preNode.val == node.val) {
                currTime++;
            } else {
                currTime = 1;
            }

            //判断当前出现次数是否比最大次数还大
            if (currTime == maxTime) {
                result.add(node.val);
            } else if (currTime > maxTime) {
                maxTime = currTime;
              	//清掉以前存放的结果
                result.clear();
                result.add(node.val);
            }
          	//很关键，别忘了向下递归的时候将当前结点赋给preNode
            preNode = node;
            inOrder(node.right);
        }
}