https://leetcode.com/problems/find-mode-in-binary-search-tree/
https://codinggeeklc.wordpress.com/2017/02/01/bst-501-find-mode-in-binary-search-tree/
https://wf94.github.io/2017/03/20/501-Find-Mode-in-Binary-Search-Tree/
如果使用附加空间的话，可以使用hash保存每个节点出现的次数。
Time complexity: O(n)
Space complexity: O(n)
http://www.cnblogs.com/grandyang/p/6436150.html
题目中的follow up说了让我们不用除了递归中的隐含栈之外的额外空间，那么我们就不能用哈希表了，不过这也不难，由于是二分搜索树，那么我们中序遍历出来的结果就是有序的，这样我们只要比较前后两个元素是否相等，就等统计出现某个元素出现的次数，因为相同的元素肯定是都在一起的。我们需要一个结点变量pre来记录上一个遍历到的结点，然后mx还是记录最大的次数，cnt来计数当前元素出现的个数，我们在中序遍历的时候，如果pre不为空，说明当前不是第一个结点，我们和之前一个结点值比较，如果相等，cnt自增1，如果不等，cnt重置1。如果此时cnt大于了mx，那么我们清空结果res，并把当前结点值加入结果res，如果cnt等于mx，那我们直接将当前结点值加入结果res，然后mx赋值为cnt。最后我们要把pre更新为当前结点
https://discuss.leetcode.com/topic/77335/proper-o-1-space
http://www.cnblogs.com/Dylan-Java-NYC/p/7088022.html
https://codinggeeklc.wordpress.com/2017/02/01/bst-501-find-mode-in-binary-search-tree/
space，time complexity都提高了，code很啰嗦，再improve一下，发现两个pass的handle value部分都差不多，合并成一个
二叉树遍历 + 计数
X.
https://www.nowtoshare.com/en/Article/Index/20475
Integer preVal=null; int count=1; int max=0; public int[] findMode(TreeNode root) { List<Integer> list =new ArrayList<>(); traverse(root,list); int[] ret = new int[list.size()]; for(int i=0; i<ret.length;i++) ret[i] =list.get(i); return ret; } public void traverse(TreeNode root, List<Integer> list) { if(root==null) return; traverse(root.left,list); if(preVal!=null) { if(preVal==root.val){ count++; } else{ count=1; } } if( count>max ) { max=count; list.clear(); list.add(root.val); } else if(max==count) { list.add(root.val); } preVal=root.val; traverse(root.right,list); }
https://discuss.leetcode.com/topic/77309/java-o-1-space-solution-beats-100
http://www.cnblogs.com/grandyang/p/6436150.html
X.
https://discuss.leetcode.com/topic/77079/java-ac-solution
https://gist.github.com/leearmee35/dbe313ce7a5d6e9144840f968e3108b8
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
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).
X.https://codinggeeklc.wordpress.com/2017/02/01/bst-501-find-mode-in-binary-search-tree/
因为follow up中要求不能使用extra space。想到bst是可以按大小顺序遍历tree的，如果需要排序，则需要inorder遍历。这样遍历一遍就可以知道mode的count是多少，有几个。再遍历第二遍，找到符合mode count的node即可。
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| int curval = 0;int curcount = 0;int[] mode;int maxcount = 0;int modecount = 0;public int[] findMode(TreeNode root) { first(root); mode = new int[modecount]; curcount = 0; modecount = 0; second(root); return mode;}private void first(TreeNode root) { if (root == null) return; first(root.left); // handle value int val = root.val; if (curval != val) { curval = val; curcount = 0; } curcount++; if (curcount > maxcount) { maxcount = curcount; modecount = 1; } else if (curcount == maxcount) { modecount++; } first(root.right); }private void second(TreeNode root) { if (root == null) return; second(root.left); // handle value int val = root.val; if (curval != val) { curval = val; curcount = 0; } curcount++; if (curcount == maxcount) { mode[modecount] = curval; modecount++; } second(root.right);} |
space，time complexity都提高了，code很啰嗦，再improve一下，发现两个pass的handle value部分都差不多，合并成一个
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
34
35
36
37
| int curval = 0;int curcount = 0;int[] mode;int maxcount = 0;int modecount = 0;public int[] findMode(TreeNode root) { inorder(root); mode = new int[modecount]; curcount = 0; modecount = 0; inorder(root); return mode;}private void handleval(int val) { if (curval != val) { curval = val; curcount = 0; } curcount++; if (curcount > maxcount) { maxcount = curcount; modecount = 1; } else if (curcount == maxcount) { if (mode != null) { mode[modecount] = curval; } modecount++; }}private void inorder(TreeNode root) { if (root == null) return; inorder(root.left); handleval(root.val); inorder(root.right);} |
如果严格利用O(1)的存储空间，需要遍历两次二叉树；第一次找到众数(mode)的数字，第二次找到符合众数个数的字符。而且如果采用非递归的方法会更佳。这里可以利用[Morris Traversal][http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html]的方法来实现。
https://blog.csdn.net/fuxuemingzhu/article/details/71124600如果使用附加空间的话，可以使用hash保存每个节点出现的次数。
题目建议不要用附加空间hash等，方法是计算了两次，一次是统计最大的模式出现的次数，第二次的时候构建出来了数组，然后把出现次数等于最大模式次数的数字放到数组的对应位置
https://zxi.mytechroad.com/blog/tree/leetcode-501-find-mode-in-binary-search-tree/Time complexity: O(n)
Space complexity: O(n)
vector<int> findMode(TreeNode* root) {
inorder(root);
return ans_;
}
private:
int val_ = 0;
int count_ = 0;
int max_count_ = 0;
vector<int> ans_;
void inorder(TreeNode* root) {
if (root == nullptr) return;
inorder(root->left);
visit(root->val);
inorder(root->right);
}
void visit(int val) {
if (count_ > 0 && val == val_) {
++count_;
} else {
val_ = val;
count_ = 1;
}
if (count_ > max_count_) {
max_count_ = count_;
ans_.clear();
}
if (count_ == max_count_)
ans_.push_back(val);
}
Two passes. First pass to find the count of the mode, second pass to collect all the modes.
Time complexity: O(n)
Space complexity: O(1)
vector<int> findMode(TreeNode* root) {
inorder(root);
mode_count_ = max_count_;
count_ = 0;
inorder(root);
return ans_;
}
private:
int val_ = 0;
int count_ = 0;
int mode_count_ = INT_MAX;
int max_count_ = 0;
vector<int> ans_;
void inorder(TreeNode* root) {
if (root == nullptr) return;
inorder(root->left);
visit(root->val);
inorder(root->right);
}
void visit(int val) {
if (count_ > 0 && val == val_) {
++count_;
} else {
val_ = val;
count_ = 1;
}
if (count_ > max_count_)
max_count_ = count_;
if (count_ == mode_count_)
ans_.push_back(val);
}
题目中的follow up说了让我们不用除了递归中的隐含栈之外的额外空间，那么我们就不能用哈希表了，不过这也不难，由于是二分搜索树，那么我们中序遍历出来的结果就是有序的，这样我们只要比较前后两个元素是否相等，就等统计出现某个元素出现的次数，因为相同的元素肯定是都在一起的。我们需要一个结点变量pre来记录上一个遍历到的结点，然后mx还是记录最大的次数，cnt来计数当前元素出现的个数，我们在中序遍历的时候，如果pre不为空，说明当前不是第一个结点，我们和之前一个结点值比较，如果相等，cnt自增1，如果不等，cnt重置1。如果此时cnt大于了mx，那么我们清空结果res，并把当前结点值加入结果res，如果cnt等于mx，那我们直接将当前结点值加入结果res，然后mx赋值为cnt。最后我们要把pre更新为当前结点
vector<int> findMode(TreeNode* root) { vector<int> res; int mx = 0, cnt = 1; TreeNode *pre = NULL; inorder(root, pre, cnt, mx, res); return res; } void inorder(TreeNode* node, TreeNode*& pre, int& cnt, int& mx, vector<int>& res) { if (!node) return; inorder(node->left, pre, cnt, mx, res); if (pre) { cnt = (node->val == pre->val) ? cnt + 1 : 1; } if (cnt >= mx) { if (cnt > mx) res.clear(); res.push_back(node->val); mx = cnt; } pre = node; inorder(node->right, pre, cnt, mx, res); }https://leetcode.com/problems/find-mode-in-binary-search-tree/discuss/98100/Java-4ms-Beats-100-Extra-O(1)-solution-No-Map
Integer prev = null;
int count = 1;
int max = 0;
public int[] findMode(TreeNode root) {
if (root == null) return new int[0];
List<Integer> list = new ArrayList<>();
traverse(root, list);
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); ++i) res[i] = list.get(i);
return res;
}
private void traverse(TreeNode root, List<Integer> list) {
if (root == null) return;
traverse(root.left, list);
if (prev != null) {
if (root.val == prev)
count++;
else
count = 1;
}
if (count > max) {
max = count;
list.clear();
list.add(root.val);
} else if (count == max) {
list.add(root.val);
}
prev = root.val;
traverse(root.right, list);
}https://discuss.leetcode.com/topic/77335/proper-o-1-space
http://www.cnblogs.com/Dylan-Java-NYC/p/7088022.html
https://codinggeeklc.wordpress.com/2017/02/01/bst-501-find-mode-in-binary-search-tree/
space，time complexity都提高了，code很啰嗦，再improve一下，发现两个pass的handle value部分都差不多，合并成一个
第一遍找出有几个mode. 建立res array, 并保留了mode duplicate次数是多少. 第二遍当duplicate次数是mode 的duplicate次数时就加入res中.
Time Complexity: O(n).
Space: O(n), 每个节点都不同, res的size就是O(n). stack space O(logn). 如果利用Binary Tree Inorder Traversal中的Morris Traversal方法可以不用stack space.
They traverse the tree in in-order and keep track of the current set of modes (among other things). But that's not O(1) space, not even when disregarding recursion stack space (as explicitly allowed) and result space (not mentioned but reasonable). The set's contents aren't on stack space, so it can't be disregarded that way. And if the values are for example 1,2,3,4,...,n-2,n-1,n-1 (unique values followed by one double value), the set grows to Ω(n) and it can't be disregarded because the result only has size 1.
I think the way to do it properly is to do two passes. One to find the highest number of occurrences of any value, and then a second pass to collect all values occurring that often. Any other ideas?
Here's a (two-pass) solution that I think can rightfully be called O(1) space. Both passes keep track of the current value etc, and the second pass additionally collects the modes in the result array. I took the value handling out of the in-order traversal into its own function for clarity. Also, this way you could very easily replace my recursive in-order traversal with for example Morris traversal. Then you wouldn't even need to disregard the recursion stack space in order to claim O(1) extra space usage.
public int[] findMode(TreeNode root) {
inorder(root);
modes = new int[modeCount];
modeCount = 0;
currCount = 0;
inorder(root);
return modes;
}
private int currVal;
private int currCount = 0;
private int maxCount = 0;
private int modeCount = 0;
private int[] modes;
private void handleValue(int val) {
if (val != currVal) {
currVal = val;
currCount = 0;
}
currCount++;
if (currCount > maxCount) {
maxCount = currCount;
modeCount = 1;
} else if (currCount == maxCount) {
if (modes != null)
modes[modeCount] = currVal;
modeCount++;
}
}
private void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
handleValue(root.val);
inorder(root.right);
}inorder function with this. I hadn't realized it earlier, but having my separate handleValue function doesn't just nicely separate the traversal logic from this problem's logic, but it's also beneficial for Morris traversal because I'm calling handleValue from two different places in the code! private void inorder(TreeNode root) {
TreeNode node = root;
while (node != null) {
if (node.left == null) {
handleValue(node.val);
node = node.right;
} else {
TreeNode prev = node.left;
while (prev.right != null && prev.right != node)
prev = prev.right;
if (prev.right == null) {
prev.right = node;
node = node.left;
} else {
prev.right = null;
handleValue(node.val);
node = node.right;
}
}
}
}二叉树遍历 + 计数
X.
https://www.nowtoshare.com/en/Article/Index/20475
Integer preVal=null; int count=1; int max=0; public int[] findMode(TreeNode root) { List<Integer> list =new ArrayList<>(); traverse(root,list); int[] ret = new int[list.size()]; for(int i=0; i<ret.length;i++) ret[i] =list.get(i); return ret; } public void traverse(TreeNode root, List<Integer> list) { if(root==null) return; traverse(root.left,list); if(preVal!=null) { if(preVal==root.val){ count++; } else{ count=1; } } if( count>max ) { max=count; list.clear(); list.add(root.val); } else if(max==count) { list.add(root.val); } preVal=root.val; traverse(root.right,list); }
https://discuss.leetcode.com/topic/77309/java-o-1-space-solution-beats-100
http://www.cnblogs.com/grandyang/p/6436150.html
Simple inorder traversal with max and curr_max to check the final arraylist.
- Inorder traversal
- If root value is equal to previous value then increase curr_max value
- If curr_max value is greater than max then clear the arraylist and store the new value
Note: I have used an array var[] to store the max, curr_max and prev. You can use the global variables as well.
void helper(TreeNode root, int[] var, List<Integer> result){
if(root == null) return;
helper(root.left,var,result);
var[1] = root.val==var[2] ? var[1]+1 : 1;
if(var[1] >= var[0]){
if(var[1] > var[0]) result.clear();
var[0] = var[1];
if(result.size()==0 || result.get(result.size()-1)!=root.val){
result.add(root.val);
}
}
var[2] = root.val;
helper(root.right,var,result);
}
//without extra space
public int[] findMode(TreeNode root) {
List<Integer> temp = new LinkedList<>();
int[] var = new int[3]; // var[0] = max, var[1] = curr_max, var[2] = prev
helper(root,var,temp);
int[] result = new int[temp.size()];
for(int i=0;i<result.length;i++) result[i] = temp.get(i);
return result;
}X.
https://discuss.leetcode.com/topic/77079/java-ac-solution
https://gist.github.com/leearmee35/dbe313ce7a5d6e9144840f968e3108b8
Map<Integer, Integer> map;
int max = 0;
public int[] findMode(TreeNode root) {
if(root==null) return new int[0];
this.map = new HashMap<>();
inorder(root);
List<Integer> list = new LinkedList<>();
for(int key: map.keySet()){
if(map.get(key) == max) list.add(key);
}
int[] res = new int[list.size()];
for(int i = 0; i<res.length; i++) res[i] = list.get(i);
return res;
}
private void inorder(TreeNode node){
if(node.left!=null) inorder(node.left);
map.put(node.val, map.getOrDefault(node.val, 0)+1);
max = Math.max(max, map.get(node.val));
if(node.right!=null) inorder(node.right);
}