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).
A:
------------inorder BST traversal, save all values in the vector<int> and then count the mode -----------------------------------Method 2, no extra space -----------------
/** * 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) { auto res = getModeAndCount(root); if(res[1] == 0) // if the count is zero { return {}; }else{ res.pop_back(); return res; } } private: vector<int> getModeAndCount(TreeNode* root) // the last is the count of mode, and the rest are mode(s) { if(not root) return {0,0}; int rootCount = getCount(root, root->val); auto L = getModeAndCount(root->left); auto R = getModeAndCount(root->right); if(L.back() == R.back()) { L.pop_back(); L.insert(L.end(), R.begin(), R.end()); }else if (L.back() < R.back()) // use L to save the more result { L = R; } if(rootCount>L.back()) { return {root->val, rootCount}; }else if (rootCount == L.back()){ L.back() = root->val; L.push_back(rootCount); } return L; } int getCount(TreeNode* root, int val) { if(not root) return 0; return (root->val == val? 1 : 0 ) + \ (root->val >= val? getCount(root->left, val) : 0 ) + \ (root->val <= val? getCount(root->right, val) : 0 ); } };
错误发生在 判断res[1] == 0 时, 一开始写成了 res.empty()
No comments:
Post a Comment