codewarrior
BAN USERvoid FindKthMax(BTNODE* root, int k)
{
if (root == NULL)
{
return;
}
std::stack<BTNODE*> stkNode;
BTNODE* p = root;
int nVisited = 0;
while (p != NULL || !stkNode.empty())
{
if (p != NULL)
{
stkNode.push(p);
p = p->rchild;
}
else
{
p = stkNode.top();
stkNode.pop();
if (++nVisited == k)
{
printf("We've got it, Kth maximum number is %c", p->chVal);
break;
}
p = p->lchild;
}
}
if (nVisited < k)
{
printf("Sorry, K overflowed.");
}
}
For finding the Kth maximum number, use reverse inorder traversal.
- codewarrior March 12, 2012Perform an inorder traversal (if find Kth minimum number) or reverse inorder traversal (if find Kth maximum number), we shall need to maintain the stack ourselves.
- codewarrior March 12, 2012Actually the lpszStart points to the first character while lpszEnd points to the last character (not the null termintaor). Here is a bug, if the sentence's first character is blank, it cannot work, and if there are more than one blanks between each word, also cannot work.
I was asked this question today in MSFT interview.
It is very simple to reverse the whole string. But if wang to reverse string and keep every word unchanged, need addition code.
#include <stddef.h>
#include <string.h>
#include <stdio.h>
#include <conio.h>
// Reverse characters within lpszStart .. lpszEnd.
void ReverseString(char* lpszStart, char* lpszEnd)
{
if (lpszStart >= lpszEnd)
{
return;
}
char* l = lpszStart;
char* r = lpszEnd;
while (l < r)
{
char ch = *l;
*l = *r;
*r = ch;
++l;
--r;
}
}
// Reverse the whole sentence, but every word is not reversed.
void ReverseSentence(char* lpszSentence)
{
if (lpszSentence == NULL)
{
return;
}
char* lpszStart = lpszSentence;
char* lpszEnd = lpszSentence + strlen(lpszSentence) - 1; // Exclude the null terminator.
ReverseString(lpszStart, lpszEnd);
// Then search word and reverse every word.
lpszStart = lpszSentence;
lpszEnd = lpszSentence;
while (true)
{
// Forward search blank character.
while (*lpszEnd != ' ' && *lpszEnd != '\0')
{
++lpszEnd;
}
// Now lpszEnd should point to a blank or null terminator.
ReverseString(lpszStart, lpszEnd-1);
if (*lpszEnd == '\0')
{
break;
}
else
{
lpszStart = ++lpszEnd;
}
}
printf(lpszSentence);
}
void main()
{
char sz[] = "hello world";
ReverseSentence(sz);
getch();
}
You didn't notice that the order of word remained unchanged.
- codewarrior March 07, 2012You didn't notice that the order of word remained unchanged.
- codewarrior March 07, 2012
I am not very clear about the question, so for every node, it have a count that equals to the number of children + 1? So N = number of nodes in left child tree + number of nodes in right child tree?
- codewarrior March 12, 2012