Problem
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 3 4 5 |
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).
Solution1: Recursion w/ extra space
Time complexity: O(n)
Space complexity: O(n)
|
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 |
// Author: Huahua // Running time: 8 ms class Solution { public: 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); } }; |
Solution2: Recursion w/o extra space
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)
|
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 |
// Author: Huahua // Running time: 8 ms class Solution { public: 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); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment