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

class TreeNode

{

public:

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int val, TreeNode* left = NULL, TreeNode *right = NULL)

{

this->val = val;

this->left = left;

this->right = right;

}

};

int GetMostFrequently(TreeNode * root)

{

void _GetMostFrequently(TreeNode *root, int & current, int & currentFrequency,

int & maxFrequency, int & mostFrequently);

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);

}