当前位置: 代码迷 >> 综合 >> Find Mode in Binary Search Tree
  详细解决方案

Find Mode in Binary Search Tree

热度:104   发布时间:2023-09-29 12:49:06.0

返回二叉树中出现次数最多的元素,可能有多个

开始想用堆栈对树进行中序遍历,存储在关联容器中,减少了运行所需的空间,但是会花费额外的时间确定最大出现次数的值。

参考discuss,用递归的方式对树进行遍历,在最后用max函数逐级比较选择最大值返回

vector<int> findMode(TreeNode* root) {unordered_map<int, int> map;vector<int> result;int modeCount = getModeCount(root, map);for(pair<int,int> p : map) {if(p.second == modeCount) {result.push_back(p.first);}}return result;}int getModeCount(TreeNode* root, unordered_map<int, int> &map) {if(root == NULL)return 0;if(map.find(root->val) == map.end()) {map.insert(pair<int, int>(root->val, 1));}else {map[root->val]++;}return max(map[root->val], max(getModeCount(root->left, map), getModeCount(root->right, map)));}


  相关解决方案