Java实现 LeetCode 501 二叉搜索树中的众数_java leetcode 501

501. 二叉搜索树中的众数

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

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如：
给定 BST [1,null,2,2],

   1
    \
     2
    /
   2
1
2
3
4
5

返回[2].

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

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

PS：
遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
      int preVal = 0, curTimes = 0, maxTimes = 0;
    ArrayList<Integer> list = new ArrayList<Integer>();
    public int[] findMode(TreeNode root) {
	traversal(root); 
	int size = list.size();
	int[] ans = new int[size];
	for(int i = 0; i < size; i++){
	    ans[i] = list.get(i);
	}
	return ans;
    }
    //二叉搜索树中序遍历是递增顺序
    public void traversal(TreeNode root){
	if(root != null){
	    traversal(root.left);
	    //判断当前值与上一个值的关系, 更新 curTimes 和 preVal
	    if(preVal == root.val){
		curTimes++;
	    }else{
		preVal = root.val;
		curTimes = 1;
	    }
	    //判断当前数量与最大数量的关系, 更新 list 和 maxTimes
	    if(curTimes == maxTimes){
		list.add(root.val);
	    }else if(curTimes > maxTimes){
		list.clear();
		list.add(root.val);
		maxTimes = curTimes;
	    }
	    traversal(root.right);
	}
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44