Google Interview - 找出二叉查找树中出现频率最高的元素

找出二叉查找树中出现频率最高的元素。树中结点满足left->val <= root->val <= right->val。如果多个元素出现次数相等，返回最小的元素。

在一个有序数组中，我们查找出现频率最高的元素，很简单，顺序扫描一遍即可统计出。那么我们对二叉查找树也可以用类似方式统计，因为中序遍历序列就是有序序列，所以我们在中序遍历的过程中就可以统计出出现频率最高的元素。

int GetMostFrequently(TreeNode *root) {  
    if(root == NULL)  
        throw new invalid_argument("Can't be a NULL tree");  
    int mostFrequently = INT_MAX;  
    int current = INT_MAX;  
    int currentFrequency = 0;  
    int maxFrequency = 0;  
    _GetMostFrequently(root, current, currentFrequency, maxFrequency, mostFrequently);  
    return mostFrequently;  
}  
  
void _GetMostFrequently(TreeNode *root, int &current, int & currentFrequency, int &maxFrequency, int &mostFrequently)  {  
    if(root == NULL)  return;  
    _GetMostFrequently(root->left, current, currentFrequency,   
                maxFrequency, mostFrequently);  
    if(root->val == current)  {
        ++currentFrequency;  
    } else  {  
        current = root->val;  
        currentFrequency = 1;  
    }  
    if(currentFrequency > maxFrequency)  {  
        maxFrequency = currentFrequency;  
        mostFrequently = current;  
    }  
    _GetMostFrequently(root->right, current, currentFrequency, maxFrequency, mostFrequently);  
} 

 

Java版本代码：

private static class Stat {
	int freq, val;
	boolean inited;
}

public int mostFrequent(TreeNode root) throws Exception {
	if(root == null) throw new Exception("null root!");
	Stat result = new Stat(), current = new Stat();
	mostFrequent(root, result, current);
	return result.val;
}

private void mostFrequent(TreeNode node, Stat result, Stat current) {
	if(node == null) return;
	mostFrequent(node.left, result, current);
	if(!current.inited || node.val != current.val) {
		current.inited = true;
		current.freq = 1;
		current.val = node.val;
	} else {
		current.freq++;
	}
	if(current.freq > result.freq) {
		result.freq = current.freq;
		result.val = current.val;
	} else if(current.freq == result.freq && current.val < result.val) {
		result.val = current.val;
	}
	mostFrequent(node.right, result, current);
}