Most Frequent Nodes in BST - Google Interview

【谷歌面试题】找出二叉查找树中出现频率最高的元素 - 计算机的艺术 - 博客频道 - CSDN.NET
找出二叉查找树中出现频率最高的元素。树中结点满足left->val <= root->val <= right->val。如果多个元素出现次数相等，返回最小的元素。
在一个有序数组中，我们查找出现频率最高的元素，很简单，顺序扫描一遍即可统计出。那么我们对二叉查找树也可以用类似方式统计，因为中序遍历序列就是有序序列，所以我们在中序遍历的过程中就可以统计出出现频率最高的元素。
http://shibaili.blogspot.com/2015/06/google-interview-questions.html

struct TreeNode{

   int val;

   TreeNode *left;

   TreeNode *right;

   TreeNode(int val) {

      this->val = val;

   }

};

 

void countNodesHelper(TreeNode *root, TreeNode *&pre, int &count, int &maxCount) {

 if (root == NULL) return;

 countNodesHelper(root->left,pre,count,maxCount);

  

 if (pre == NULL) {

    pre = root;

    count = 1;

   

 }else {

    if (pre->val == root->val) {

       count++;

       if (maxCount < count) {

          maxCount = count;

       }

    }else {

       count = 1;

    }

 }

   pre = root;

   countNodesHelper(root->right,pre,count,maxCount);

}

 

int countNodes(TreeNode *root) {

   int maxCount = 0,count = 0;

   TreeNode *pre = NULL;

   foo(root,pre,count,maxCount);

   return maxCount;

}

1. class TreeNode  
2. {  
3. public:  
4.     int val;  
5.     TreeNode *left;  
6.     TreeNode *right;  
7.     TreeNode(int val, TreeNode* left = NULL, TreeNode *right = NULL)  
8.     {  
9.         this->val = val;  
10.         this->left = left;  
11.         this->right = right;  
12.     }  
13. };  
14.   
15. int GetMostFrequently(TreeNode * root)  
16. {  
17.     void _GetMostFrequently(TreeNode *root, int & current, int & currentFrequency,   
18.                 int & maxFrequency, int & mostFrequently);  
19.     if(root == NULL)  
20.         throw new invalid_argument("Can't be a NULL tree");  
21.     int mostFrequently = INT_MAX;  
22.     int current = INT_MAX;  
23.     int currentFrequency = 0;  
24.     int maxFrequency = 0;  
25.     _GetMostFrequently(root, current, currentFrequency, maxFrequency, mostFrequently);  
26.     return mostFrequently;  
27. }  
28.   
29. void _GetMostFrequently(TreeNode *root, int & current, int & currentFrequency,   
30.             int & maxFrequency, int & mostFrequently)  
31. {  
32.     if(root == NULL)  
33.         return;  
34.     _GetMostFrequently(root->left, current, currentFrequency,   
35.                 maxFrequency, mostFrequently);  
36.     if(root->val == current)  
37.         ++currentFrequency;  
38.     else  
39.     {  
40.         current = root->val;  
41.         currentFrequency = 1;  
42.     }  
43.     if(currentFrequency > maxFrequency)  
44.     {  
45.         maxFrequency = currentFrequency;  
46.         mostFrequently = current;  
47.     }  
48.     _GetMostFrequently(root->right, current, currentFrequency,   
49.                 maxFrequency, mostFrequently);  
50. }  

Read full article from 【谷歌面试题】找出二叉查找树中出现频率最高的元素 - 计算机的艺术 - 博客频道 - CSDN.NET