Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than or equal to the node's key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
- Both the left and right subtrees must also be binary search trees.
For example:
Given BST [1,null,2,2],
1
\
2
/
2
return [2].
Note: If a tree has more than one mode, you can return them in any order.
Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
解题：给一个二叉查找树，返回出现次数最多的元素（众数）。并且要求不使用额外的空间，要求结果以数组的形式返回。我使用了一个ArrayList，有额外的空间消耗，虽然不满足条件，但是比较简单方便。当然也可以把数组定义为成员变量，由于数组的长度不知道，还得定义一个末尾指针，太麻烦，不如用集合。思路是，遍历BST，由于其本身的性质，遍历的过程中得到的序列，就是一个有序序列。定一个max用来保存出现做多的次数，pre记录父节点，如果没有，则为空。再定义一个res的集合保存结果，定一个cns保存当前出现最多的次数（暂时），然后不断地比较cns和max的值，随时更新res结果集，代码如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
ArrayList<Integer>res = null;
TreeNode pre = null;
int max = 0;
int cns = 1;
public int[] findMode(TreeNode root) {
//存放结果
res = new ArrayList<Integer>();
middle_search(root);
int[] arr =new int[res.size()];
for(int i =0; i < arr.length; i++)
arr[i] = res.get(i);
return arr;
}
public void middle_search(TreeNode root) {
if(root == null)
return ;
middle_search(root.left);
//处理根结点
if(pre != null){ //有父节点
if(root.val == pre.val)
cns++;
else cns = 1;
}
if(cns >= max){
if(cns > max)
res.clear();
max = cns;
res.add(root.val);
}
pre = root; middle_search(root.right);
}
}