[돌머리] 돌머리를 깨기 위한 간단한 알고리즘 문제 – BST에서 중복 개수 새기

Write an algorithm to print out how many extra duplicates there are in a binary search tree. and using global value for count and value

 

example]

———– 3

—2—————– 3

– 1 —2 ——————4

———————3 ———4

————————————–5

———————————————–5

output :

2  1

3  2

4  1

5  1

 

solve) Focus on, O(n) time complexity and O(1) space just travel this BST tree using inorder sequence.

 

void _traversePrint(Node *node){
 if( node->left ){
 _traversePrint(node->left);
 }

if( count && (value == node->data) ){
 count++;
 }else{
 if( count > 1 ){
 printf("(%d):(%d)\n", value, count);
 value = node->data;
 count = 1;
 }else{
 count = 1;
 value = node->data;
 }
 }

if( node->right ){
 _traversePrint(node->right);
 }

if( node == root && count > 1 ){
 printf("(%d):(%d)\n", value, count);
 }
 }