LeetCode Find Mode in Binary Search Tree 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.
[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).
找到二叉搜索树中所有的众数，如果有多个众数，都要给出。并且Follow up限制空间复杂度为O(1)。 很有意思的一个题，如果把二叉搜索树当成一棵普通的树，并且没有O(1)空间复杂度的限制，则在遍历时，可以使用hash统计每个数出现的频率，然后取最高频率的数。代码如下： [cpp] class Solution { public: void work(unordered_map<int, int>& hash, TreeNode* root, int& modCnt) { if (root == NULL)return; ++hash[root->val]; modCnt = max(modCnt, hash[root->val]); work(hash, root->left, modCnt); work(hash, root->right, modCnt); } vector<int> findMode(TreeNode* root) { unordered_map<int, int> hash; int modCnt = INT_MIN; work(hash, root, modCnt); vector<int> ans; unordered_map<int, int>::iterator it = hash.begin(); while (it != hash.end()) { if (it->second == modCnt)ans.push_back(it->first); ++it; } return ans; } }; [/cpp] 本代码提交AC，用时25MS。 如果使用二叉搜索树的特点并且考虑O(1)的空间复杂度，就有点复杂了。因为二叉搜索树的左孩子小于等于根节点，根节点小于等于右孩子，所以如果对二叉搜索树中序遍历的话，得到的序列就是一个非递减序列，也就是说是一个有序序列，那就好办多了。比如给定序列[1,2,2,3,4,4,5,6]，要找出数组中的众数，并且限制O(1)空间复杂度，应该就不难了。 因为要O(1)空间复杂度，就不能用hash统计频率了，因为众数可能有多个，我们没法在一次遍历时就既找到最大的频率，又找到众数，所以可以采取两次遍历的策略。第一遍先找到最大的频率，上面的例子中是2（2和4都出现了两次）；第二遍再把频率等于2的数值找出来，就是众数了。 对应到二叉搜索树中，就是对树中序遍历两次，第一次得到最大的频率以及众数的个数，第二遍再把所有众数都找出来。代码如下： [cpp] class Solution { private: vector<int> mods; int curVal = 0, curCnt = 0, modCnt = 0, maxCnt = 0; void handleValue(int v) { if (v != curVal) { curVal = v; curCnt = 0; } ++curCnt; if (curCnt > maxCnt) { // 第二次遍历时不会走此分支 maxCnt = curCnt; modCnt = 1; } else if (curCnt == maxCnt) { if (!mods.empty())mods[modCnt] = curVal; ++modCnt; } } void inorder(TreeNode* root) { if (root == NULL)return; inorder(root->left); handleValue(root->val); inorder(root->right); } public: vector<int> findMode(TreeNode* root) { inorder(root); mods.resize(modCnt); curCnt = 0; modCnt = 0; inorder(root); return mods; } }; [/cpp] 本代码提交AC，用时19MS。 参考：https://discuss.leetcode.com/topic/77335/proper-o-1-space]]>