r******j
发帖数: 92 | 1 回报本版，发新鲜面经。今年第一面结束。move on了。下面这题就没搞出来。
Given: node.getParent(), node.getNextSibling(), node.getFirstChild()
Implement: getNextNode(node)
For example:
1
1.1
1.1.1
1.1.2
1.2
2
3
就是像章节序列一样的一个tree。
其他的都是常见题，
increment one;
count frequency of number in a list;
merge two sorted array and remove duplicate;
pow(int x, int y); |
x****g
发帖数: 1512 | 2 是要这个?
有子节点,返回子节点.
没子节点,看兄弟节点.
没兄弟开始回溯父节点找父节点兄弟,找到或者到根退出?
唯一需要注意的是第3个持续回溯的可能?
getNextNode(node)
{
if(node==NULL) return null;
Node* next = node->getFirstChild();
if(next) return next;
next = node->getSlibing();
if(next) return next;
next = node->getParent();
while(next)
{
next = next->getSlibing();
if(next) return next;
next = next->getParent();
}
return NULL;
} |
P*****f
发帖数: 2272 | 3 对，不过参数node为null时，抛出异常或者返回错误编码更好
【在 x****g 的大作中提到】
: 是要这个?
: 有子节点,返回子节点.
: 没子节点,看兄弟节点.
: 没兄弟开始回溯父节点找父节点兄弟,找到或者到根退出?
: 唯一需要注意的是第3个持续回溯的可能?
: getNextNode(node)
: {
: if(node==NULL) return null;
: Node* next = node->getFirstChild();
: if(next) return next;
|
r******j
发帖数: 92 | 4 你们是对的。哎，面试时一根筋了，总在想recursive的解。。。。 |
w*****h
发帖数: 423 | 5 多谢LZ~~
increment 1是什么意思？
【在 r******j 的大作中提到】
: 回报本版，发新鲜面经。今年第一面结束。move on了。下面这题就没搞出来。
: Given: node.getParent(), node.getNextSibling(), node.getFirstChild()
: Implement: getNextNode(node)
: For example:
: 1
: 1.1
: 1.1.1
: 1.1.2
: 1.2
: 2
|
m****r
发帖数: 120 | 6 可能是plus one那题
【在 w*****h 的大作中提到】
: 多谢LZ~~
: increment 1是什么意思？
|
m*******4
发帖数: 34 | 7 Bless!请问count frequency是什么意思，能再详解说一下吗？ |
l******a
发帖数: 64 | 8 是统计词频吧
【在 m*******4 的大作中提到】
: Bless!请问count frequency是什么意思，能再详解说一下吗？
|
S*A
发帖数: 7142 | 9 也写来玩玩。
struct node *getNextNode(struct node * node)
{
struct node * next;
assert(node);
if ((next = getFirstChild(node)))
return next;
while (node) {
if ((next = getNextSibling(node)))
return next;
node = getParent(node);
}
return NULL;
}
【在 x****g 的大作中提到】
: 是要这个?
: 有子节点,返回子节点.
: 没子节点,看兄弟节点.
: 没兄弟开始回溯父节点找父节点兄弟,找到或者到根退出?
: 唯一需要注意的是第3个持续回溯的可能?
: getNextNode(node)
: {
: if(node==NULL) return null;
: Node* next = node->getFirstChild();
: if(next) return next;
|
A*****o
发帖数: 284 | 10 struct TreeNode {
int val;
vector children;
TreeNode* getParent();
TreeNode* getNextSibling();
TreeNode* getFirstChild();
};
TreeNode* getNextNode(TreeNode *node) {
if (!node) return NULL;
TreeNode *r = node->getFirstChild();
if (r) return r;
r = node->getNextSibling();
if (r) return r;
r = r->getParent();
while (r) {
r = r->getNextSibling();
if (r) return r;
r = r->getParent();
}
return NULL;
} |
w*******i
发帖数: 186 | 11 while循环写错了吧，
while (r) {
r = r->getNextSibling();
if (r) return r;
r = r->getParent();
}
如果r没有sibling，那么在循环里第二句r会为NULL，调用r->getParent()会报错
的。
可以改成
TreeNode* ancestor = r->getParent();
while (ancestor && !ancestor.getNextSibling())
ancestor = ancestor.getParent();
if (ancestor)
return ancestor.getNextSibling();
else
return null;
【在 A*****o 的大作中提到】
: struct TreeNode {
: int val;
: vector children;
: TreeNode* getParent();
: TreeNode* getNextSibling();
: TreeNode* getFirstChild();
: };
: TreeNode* getNextNode(TreeNode *node) {
: if (!node) return NULL;
: TreeNode *r = node->getFirstChild();
|
