jinil
BAN USERstring getSequence(string target){
int curRow = 0, curCol = 0;
string ans = "";
for(int i=0; i<target.size(); i++){
int chNum = target[i] - 'a';
int row = chNum / 5;
int col = chNum % 5;
while(curRow != row){
if(curRow > row){
curRow--;
ans += 'u';
}else{
curRow++;
ans += 'd';
}
}
while(curCol != col){
if(curCol > col){
curCol--;
ans += 'l';
}else{
curCol++;
ans += 'r';
}
}
ans += '!';
}
return ans;
}
I agree with brighama's saying. If we traverse this BST with Inorder, we can consider this is sorted array. Then we can get the most frequent node in [ Time : O(n), Space : O(1) ]. This is the code using C++.
#include <iostream>
using namespace std;
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int val_)
:val(val_), left(NULL), right(NULL){}
};
int maxFreqVal;
int maxFreqCount;
void inorder(TreeNode *node, int &curFreqVal, int &curFreqCount){
if(node == NULL)
return;
inorder(node->left, curFreqVal, curFreqCount);
if(curFreqVal != node->val){
curFreqVal = node->val;
curFreqCount = 1;
}else{
curFreqCount++;
if(curFreqCount > maxFreqCount){
maxFreqVal = curFreqVal;
maxFreqCount = curFreqCount;
}
}
inorder(node->right, curFreqVal, curFreqCount);
}
int getFreq(TreeNode *root){
if(root == NULL)
return -1;
maxFreqVal = root->val;
maxFreqCount = 1;
int curFreqVal = root->val;
int curFreqCount = 1;
inorder(root, curFreqVal, curFreqCount);
return maxFreqVal;
}
int main(){
TreeNode *root = new TreeNode(10);
root->right = new TreeNode(12);
root->right->left = new TreeNode(12);
root->right->left->left = new TreeNode(12);
root->right->left->right = new TreeNode(12);
root->right->right = new TreeNode(12);
root->right->right->left = new TreeNode(12);
root->right->right->right = new TreeNode(12);
root->left = new TreeNode(6);
root->left->left = new TreeNode(6);
root->left->left->left = new TreeNode(4);
root->left->left->right = new TreeNode(6);
root->left->right = new TreeNode(6);
root->left->right->left = new TreeNode(6);
root->left->right->right = new TreeNode(6);
root->left->right->right->right = new TreeNode(7);
int result = getFreq(root);
cout << "result : " << result << ", frequency : " << maxFreqCount << endl;
return 0;
}
Hi, Sid.
- jinil April 28, 2013Thank you for your pointing!!
Yes, you are right. The solution didn't control the special case.
Thus I modified 'saving the result' part in the 'inorder' method.
And I added more Node to test this case. You can test it! Thanks!!