Google Interview - 找出二叉查找树中出现频率最高的元素 - 我的博客 - ITeye技术网站

Google Interview - 找出二叉查找树中出现频率最高的元素 - 我的博客 - ITeye技术网站

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

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

1. int GetMostFrequently(TreeNode *root) {    
2.     if(root == NULL)    
3.         throw new invalid_argument("Can't be a NULL tree");    
4.     int mostFrequently = INT_MAX;    
5.     int current = INT_MAX;    
6.     int currentFrequency = 0;    
7.     int maxFrequency = 0;    
8.     _GetMostFrequently(root, current, currentFrequency, maxFrequency, mostFrequently);    
9.     return mostFrequently;    
10. }    
11.     
12. void _GetMostFrequently(TreeNode *root, int &current, int & currentFrequency, int &maxFrequency, int &mostFrequently)  {    
13.     if(root == NULL)  return;    
14.     _GetMostFrequently(root->left, current, currentFrequency,     
15.                 maxFrequency, mostFrequently);    
16.     if(root->val == current)  {  
17.         ++currentFrequency;    
18.     } else  {    
19.         current = root->val;    
20.         currentFrequency = 1;    
21.     }    
22.     if(currentFrequency > maxFrequency)  {    
23.         maxFrequency = currentFrequency;    
24.         mostFrequently = current;    
25.     }    
26.     _GetMostFrequently(root->right, current, currentFrequency, maxFrequency, mostFrequently);    
27. }   

1. private static class Stat {  
2.     int freq, val;  
3.     boolean inited;  
4. }  
5.   
6. public int mostFrequent(TreeNode root) throws Exception {  
7.     if(root == null) throw new Exception("null root!");  
8.     Stat result = new Stat(), current = new Stat();  
9.     mostFrequent(root, result, current);  
10.     return result.val;  
11. }  
12.   
13. private void mostFrequent(TreeNode node, Stat result, Stat current) {  
14.     if(node == null) return;  
15.     mostFrequent(node.left, result, current);  
16.     if(!current.inited || node.val != current.val) {  
17.         current.inited = true;  
18.         current.freq = 1;  
19.         current.val = node.val;  
20.     } else {  
21.         current.freq++;  
22.     }  
23.     if(current.freq > result.freq) {  
24.         result.freq = current.freq;  
25.         result.val = current.val;  
26.     } else if(current.freq == result.freq && current.val < result.val) {  
27.         result.val = current.val;  
28.     }  
29.     mostFrequent(node.right, result, current);  
30. }  

Read full article from Google Interview - 找出二叉查找树中出现频率最高的元素 - 我的博客 - ITeye技术网站