s******5
发帖数: 673 | 1 New York office. With a guy from "research team".
1. How do you find two strings are anagrams
2. How do you find a node after a given node in a BST(pre-order traversal).
Wrote code in google docs. I think I got those correctly. However, got
rejected in 2 hours. :( |
i******s
发帖数: 301 | |
s******5
发帖数: 673 | 3
too late la...:)
"However, got rejected in 2 hours. :("
【在 i******s 的大作中提到】
: bless
|
s****n
发帖数: 150 | 4 bless
traversal).
got
【在 s******5 的大作中提到】
: New York office. With a guy from "research team".
: 1. How do you find two strings are anagrams
: 2. How do you find a node after a given node in a BST(pre-order traversal).
: Wrote code in google docs. I think I got those correctly. However, got
: rejected in 2 hours. :(
|
t*******0
发帖数: 16 | 5 1. Find the given node, add the track to stack
2. Find next right node
void findnextnode(BinaryTree *root, int node_val)
{
stack s;
int error = 0;
BinaryTree *cur = root;
BinaryTree *cur = NULL;
//Find match node
while(cur!=NULL)
{
s.push(cur);
if(cur->value==node_val)
break;
else if((cur->valueright!=NULL))
{
cur = cur->right;
}
else if((cur->value>node_val)&&(cur->left!=NULL))
{
cur = cur->left;
}
else
{
error = 1;
break;
}
}
if(error==0)
{
error = 1;
cur = s.top();
while(!s.empty)
{
cur = s.top();
if((cur->right!=NULL)&&(cur->right!=prev))
{
cur = cur->right;
while(cur->left!=NULL)
cur = cur->left;
cout<<"Next node value is"<value;
error = 0;
break;
}
else
{
prev=cur;
s.pop();
}
}
if(error==1)
cout<<"No Next right node value";
}
else
cout<<"Cannot find node with value: "<
} |
e********s
发帖数: 248 | 6 Your code seems to work for inorder instead of preorder, am I right?
【在 t*******0 的大作中提到】
: 1. Find the given node, add the track to stack
: 2. Find next right node
: void findnextnode(BinaryTree *root, int node_val)
: {
: stack s;
: int error = 0;
: BinaryTree *cur = root;
: BinaryTree *cur = NULL;
: //Find match node
: while(cur!=NULL)
|
t*******0
发帖数: 16 | 7 Yes, it is the in-order traversal after getting the given node |
e********s
发帖数: 248 | 8 I mean the question actually asks for preorder traversal.
【在 t*******0 的大作中提到】
: Yes, it is the in-order traversal after getting the given node
|
t*******0
发帖数: 16 | 9 Not quite undertand
You mean implement a pre-order traverse function and at the mean time find
the next right of a given node? |
e********s
发帖数: 248 | 10 This is the original question:
2. How do you find a node after a given node in a BST(pre-order traversal).
【在 t*******0 的大作中提到】
: Not quite undertand
: You mean implement a pre-order traverse function and at the mean time find
: the next right of a given node?
|
A*H
发帖数: 127 | 11
traversal).
a node after a given node
4
/ \
2 5
/ \
1 3
input->output
4->2
2->1
1->3
3->5
【在 e********s 的大作中提到】
: This is the original question:
: 2. How do you find a node after a given node in a BST(pre-order traversal).
|
d***8
发帖数: 1552 | 12 BinaryTree* findnextnode(BinaryTree *root, int node_val)
{
stack stk;
BinaryTree *cur = root;
//Find match node
while(cur != NULL)
{
stk.push(cur);
if(cur->value == node_val)
break;
else if (cur->value < node_val)
cur = cur->right;
else if(cur->value > node_val)
cur = cur->left;
}
if (cur == NULL)
{
cout << "Cannot find node with value: " << node_val;
return NULL;
}
else
{
if (cur->left)
return cur->left;
else if (cur->right)
return cur->right;
else //leaf node
{
stk.pop();
BinaryTree* parent;
if (!stk.empty())
{
parent = stk.top();
stk.pop();
}
else
return NULL;
while(!(cur == parent->left && parent->right))
{
cur = parent;
if (!stk.empty())
{
parent = stk.top();
stk.pop();
}
else
return NULL;
};
return parent->right;
}
}
} |
