这题是让求二叉搜索树中的众数,也就是出现次数最多的那个数。如果是在一个排序的数 组中找众数,这个可能就比较简单,但这题是让在二叉搜索树中查找。
我们都知道二叉搜索树的中序遍历是有序的,有一种方式就是先把二叉搜索树中序遍历的 结果存放到一个数组中,因为这个数组是升序的(虽然有重复的),我们可以遍历这个数 组,这里使用几个变量。
使用变量curent表示当前的值,count表示当前值的数量,maxCount表示重复数字最 大的数量。l i s t集合存放结果。
如果当前节点的值等于curent,count就加1
如果当前节点的值不等于current,说明遇到了下一个新的值,更新current为新的 值,然后让count=1;
接着比较count和maxCount的大小
如果count==ma xCount,就把当前节点的值加入到集合l i s t中。
如果count>ma xCount,说明遇到重复次数最高的数了,这里先把l i s t集合清空,然后 再把当前节点的值加入到集合l i s t中,最后在更新ma xCount的值。
List<Integer> list = new ArrayList();int count = 0; //表示当前节点的值int maxCount = 0; //和当前节点值相同的节点数量int currentValue = 0; //最大的重复数量public int[] findMode(TreeNode root) {inorder(root);int[] res = new int[list.size()];for (int i = 0; i < list.size(); i++) {res[i] = list.get(i);}return res;}public void inorder(TreeNode root) {if (root == null) return ;// 遍历左子树inorder(root.left);if (root.val == currentValue) {// 如果节点值等于curent,count就加1count++;} else {// 否则,就表示遇到了一个新的值,curent和count都要// 重新赋值currentValue = root.val;count = 1;}if (count == maxCount) {// 如果count == maxCount,就把当前节点加入到集合中list.add(root.val);} else if (count > maxCount) {// 否则,当前节点的值重复量是最多的,直接把list清空,然后// 把当前节点的值加入到集合中list.clear();list.add(root.val);maxCount = count;}inorder(root.right);}
