LeetCode501 Find Mode in Binary Search Tree

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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.

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

样例

1
2
3
4
5
6
7
8
9
Input:
Given BST [1,null,2,2],
1
\
2
/
2
Output:
2

思路

找出二叉搜索树中的众数。

直观的想法是,遍历一遍二叉搜索树,用哈希表来记录每个数出现的次数,维护一个最大值,最后遍历哈希表找出众数即可。这个方法需要申请额外的空间,并且也没有用到BST的性质。

根据二叉搜索树的性质,我们使用中序遍历其实可以得到一个有序的结果。那么问题就转化为:给一个单调递增的数组,找出其中的众数。该问题只需要遍历一遍数组,将每个元素与其前驱元素比较是否相等,然后维护出现次数的最大值,不需要额外空间即可找到众数。

代码

哈希表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* 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:
unordered_map<int, int> Map;
int maxCnt;
void dfs(TreeNode* root) {
if (root == nullptr) return ;
maxCnt = max(maxCnt, ++Map[root->val]);
dfs(root->left);
dfs(root->right);
}
vector<int> findMode(TreeNode* root) {
Map.clear();
maxCnt = 0;
dfs(root);
vector<int> ans;
for (auto& x: Map) {
if (x.second == maxCnt) {
ans.push_back(x.first);
}
}
return ans;
}
};

无需额外空间:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* 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:
int maxCnt, curCnt;
TreeNode* preNode;
void inOrder(TreeNode* root, vector<int>& ans) {
if (root == nullptr) return ;
inOrder(root->left, ans);
if (preNode) curCnt = (preNode->val == root->val) ? curCnt + 1 : 1;
if (curCnt >= maxCnt) {
if (curCnt > maxCnt) ans.clear();
ans.push_back(root->val);
maxCnt = curCnt;
}
preNode = root;
inOrder(root->right, ans);
}
vector<int> findMode(TreeNode* root) {
preNode = nullptr;
maxCnt = 0, curCnt = 1;
vector<int> ans;
inOrder(root, ans);
return ans;
}
};
分享到 评论