# 【谷歌面试题】找出二叉查找树中出现频率最高的元素

[cpp]
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. int GetMostFrequently(TreeNode * root)
15. {
16.     void _GetMostFrequently(TreeNode *root, int & current, int & currentFrequency,
17.                 int & maxFrequency, int & mostFrequently);
18.     if(root == NULL)
19.         throw new invalid_argument(“Can’t be a NULL tree”);
20.     int mostFrequently = INT_MAX;
21.     int current = INT_MAX;
22.     int currentFrequency = 0;
23.     int maxFrequency = 0;
24.     _GetMostFrequently(root, current, currentFrequency, maxFrequency, mostFrequently);
25.     return mostFrequently;
26. }
27. void _GetMostFrequently(TreeNode *root, int & current, int & currentFrequency,
28.             int & maxFrequency, int & mostFrequently)
29. {
30.     if(root == NULL)
31.         return;
32.     _GetMostFrequently(root->left, current, currentFrequency,
33.                 maxFrequency, mostFrequently);
34.     if(root->val == current)
35.         ++currentFrequency;
36.     else
37.     {
38.         current = root->val;
39.         currentFrequency = 1;
40.     }
41.     if(currentFrequency > maxFrequency)
42.     {
43.         maxFrequency = currentFrequency;
44.         mostFrequently = current;
45.     }
46.     _GetMostFrequently(root->right, current, currentFrequency,
47.                 maxFrequency, mostFrequently);
48. }