|
|---|
|
|
|
|
|
|
s*********t
发帖数: 52 | 1 电面一家最近比较火的startup
实现二叉树的postorder traversal，我就写啊，递归，很快搞定，十行左右，然后面
试官说不用写这么多四、五就能搞定，想了想也改好了。
follow up，不用递归，我就改啊，while循环，有个小错误，他提示之后，也写好了。
又follow up，在while循环的基础上，写getfirst函数，找到postorder的第一个node
指针，然后写个getnext函数，根据第一个接着一个一个找下去。我问能不能有额外内
存或者可不可以改变二叉树，比如删节点，回答说不行。然后就悲剧了，实在想不出
getnext怎么写，最后把getfirst写好就到时间了。现在想想，单向的二叉树不可能实
现吧？！嗨，当时应该多问一句是不是双向的。 | s*******s
发帖数: 1031 | 2 做了一下，不知道对不对。
void PostVisit(TreeNode *tree) {
if(!tree)
return;
PostVisit(tree->left);
PostVisit(tree->right);
print(tree->value);
}
void PostVisit(TreeNode *tree) {
if(!tree)
return;
stack stkNodes;
stkNodes.push(tree);
while(!stkNodes.empty()) {
TreeNode *node = stkNodes.top();
if(node->left)
stkNodes.push(node->left);
else if(node->right)
stkNodes.push(node->right);
else {
visit(node);
stkNodes.pop();
while(!stkNodes.empty()) {
TreeNode *parent = stkNodes.top();
if(!parent->right || node==parent->right) {
visit(parent)
node = parent;
stkNodes.pop();
} else {
stkNodes.push(parent->right);
break;
}
}
}
}
}
TreeNode *getFirst(TreeNode *root) {
if(!root)
return NULL;
TreeNode *node = root;
while(node->left)
node = node->left;
return node;
}
TreeNode *getNext(TreeNode *root, TreeNode *pre) {
if(!tree)
return;
bool bReturnNode = false;
stack stkNodes;
stkNodes.push(tree);
while(!stkNodes.empty()) {
TreeNode *node = stkNodes.top();
if(node == pre)
bReturnNode = true;
if(node->left)
stkNodes.push(node->left);
else if(node->right)
stkNodes.push(node->right);
else {
if(bReturnNode && node!=pre)
return node;
visit(node);
stkNodes.pop();
while(!stkNodes.empty()) {
TreeNode *parent = stkNodes.top();
if(!parent->right || node==parent->right) {
if(bReturnNode && parent!=pre)
return parent;
visit(parent)
node = parent;
stkNodes.pop();
} else {
stkNodes.push(parent->right);
break;
}
}
}
}
return NULL;
}
node
【在 s*********t 的大作中提到】
: 电面一家最近比较火的startup
: 实现二叉树的postorder traversal，我就写啊，递归，很快搞定，十行左右，然后面
: 试官说不用写这么多四、五就能搞定，想了想也改好了。
: follow up，不用递归，我就改啊，while循环，有个小错误，他提示之后，也写好了。
: 又follow up，在while循环的基础上，写getfirst函数，找到postorder的第一个node
: 指针，然后写个getnext函数，根据第一个接着一个一个找下去。我问能不能有额外内
: 存或者可不可以改变二叉树，比如删节点，回答说不行。然后就悲剧了，实在想不出
: getnext怎么写，最后把getfirst写好就到时间了。现在想想，单向的二叉树不可能实
: 现吧？！嗨，当时应该多问一句是不是双向的。
| p*****2
发帖数: 21240 | | s*********t
发帖数: 52 | 4 getnext只能有一个输入参数
【在 s*******s 的大作中提到】
: 做了一下，不知道对不对。
: void PostVisit(TreeNode *tree) {
: if(!tree)
: return;
: PostVisit(tree->left);
: PostVisit(tree->right);
: print(tree->value);
: }
: void PostVisit(TreeNode *tree) {
: if(!tree)
| h***u
发帖数: 9 | |
|
|
|
|
|
|
