# LeetCode501. Find Mode in Binary Search Tree（二分搜索树 / 模拟）

## LeetCode501. Find Mode in Binary Search Tree（二分搜索树 / 模拟）

• Easy
• Accepted：51,648
• Submissions：132,574

Given a binary search tree (BST) with duplicates, find all the mode(s)) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than or equal to the node's key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
• Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

   1
\
2
/
2

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

### 链接

https://leetcode.com/problems/find-mode-in-binary-search-tree

### 代码

• Runtime: 28 ms, faster than 98.44% of C++ online submissions for Find Mode in Binary Search Tree.
• Memory Usage: 23.5 MB, less than 59.22% of C++ online submissions for Find Mode in Binary Search Tree.
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> findMode(TreeNode* root) {
inorder(root);
return ans;
}

private:
vector <int> ans;
int maxCnt = 0, tmpCnt = 0, curVal; // 出现最大次数，当前元素出现次数，当前元素
void inorder(TreeNode* root)
{
if (root == NULL)
return ;
inorder(root->left);
++tmpCnt;
if (curVal != root->val) // 不为同一个值，更新
{
curVal = root->val;
tmpCnt = 1;
}
if (tmpCnt > maxCnt) // 更新maxCnt
{
maxCnt = tmpCnt;
ans.clear();
ans.push_back(curVal);
}
else if (tmpCnt == maxCnt) // 多个maxCnt
ans.push_back(curVal);
inorder(root->right);
}
};

### 参考

https://blog.csdn.net/liuchuo/article/details/54854037

The end.
2019年3月14日 星期四