l****c
发帖数: 782 | 1 If there is an tree structure data, design an algorithm for function next()
which returns one data each time and this function will access all the data
only once.
大家用什么方法呢？ |
C***U
发帖数: 2406 | 2 是说tree的node只access一次吧 但是可以把数据存起来吧？
这个好像我身边有个人被微软问到了
用bfs 或者dfs可以吧
)
data
【在 l****c 的大作中提到】
: If there is an tree structure data, design an algorithm for function next()
: which returns one data each time and this function will access all the data
: only once.
: 大家用什么方法呢？
|
l****c
发帖数: 782 | 3 我也不是很清楚，题就是这样些的。
dfs，不也需要一个visited来记录吗？那就是需要走两遍了。
我的理解是用recursion的in order遍历。要是non-recursion就需要stack了，就有节
点走了2遍；recursion的算不算1遍呢？
【在 C***U 的大作中提到】
: 是说tree的node只access一次吧 但是可以把数据存起来吧？
: 这个好像我身边有个人被微软问到了
: 用bfs 或者dfs可以吧
:
: )
: data
|
C***U
发帖数: 2406 | 4 bfs就不用visit两遍啊 把他们都放到queue里面去
【在 l****c 的大作中提到】
: 我也不是很清楚，题就是这样些的。
: dfs，不也需要一个visited来记录吗？那就是需要走两遍了。
: 我的理解是用recursion的in order遍历。要是non-recursion就需要stack了，就有节
: 点走了2遍；recursion的算不算1遍呢？
|
l****c
发帖数: 782 | 5 这题，用bfs能解吗？
【在 C***U 的大作中提到】
: bfs就不用visit两遍啊 把他们都放到queue里面去
|
s********o
发帖数: 861 | 6 用 BFS
static {
Queue queue;
queue.enqueue(root);
}
Node next() {
Node x = queue.dequeue();
if (x != null) {
for (Node c: x.children()) {
queue.enqueue(c);
}
}
return x;
} |
w****x
发帖数: 2483 | 7 struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
class CIterator
{
public:
CIterator(NODE* pRoot)
{
pushLft(pRoot);
}
NODE* GetNext()
{
if (m_stk.empty()) return NULL;
NODE* pRet = stk.top();
stk.pop();
pushLft(pRet->pRgt);
return pRet
}
private:
void pushLft(NODE* pNode)
{
NODE* pIter = pNode;
while (NULL != pIter)
{
m_stk.push_back(pIter);
pIter = pIter->pLft;
}
}
private:
stack m_stk;
}; |
l****c
发帖数: 782 | 8 太强了吧～我完全不会这种利用C++ class的方法，怎么学来的啊大牛～
【在 w****x 的大作中提到】
: struct NODE
: {
: int nVal;
: NODE* pLft;
: NODE* pRgt;
:
: NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
: };
: class CIterator
: {
|
r*******h
发帖数: 127 | 9 这个是binary tree in order traversal的non recursion解法吗？
【在 w****x 的大作中提到】
: struct NODE
: {
: int nVal;
: NODE* pLft;
: NODE* pRgt;
:
: NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
: };
: class CIterator
: {
|
