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

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

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

[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. }

标签