脸熟跪经

张欣 发表于 2017-9-28 07:27
请问楼主，第二题是不是可以从头开始挨个读，读到第一s1就先s1存到stack，接着读s1 的child pointer的链表 ...

我也想的是用stack， 但是试了下感觉逻辑有点乱

第二题只想到用queue做。有不需要额外空间的做法吗？

同意楼上，用一个Queue应该可以解决啊

第二题 dfs recursive 不用class variable的话每次返回updated tail应该可以吧。iterative 用一个stack，每次先push next 再push child应该也可以。多谢楼主分享。

第二题如果是recursive来做，不用全局的话，就先save next，然后把s的flatten之后，再找到当前tail换成next可以吗? 代码大概是这样
Node* flattenList(Node* node, Node* s)
{
    if (node == NULL)
        return NULL;
       
        Node* head = new Node(0);
        head->next = node;

        Node* cur = head;
        while (cur->next && cur->next != s) cur = cur->next;
        if (cur->next == s) {
                        Node *next = cur->next->next;
                        cur->next = flattenList(s->child);
                        if (next)
                                        while (cur->next) cur = cur->next;
                                        cur->next = flattenList(next, s);
        }

    return head->next;
}

或者可以想成是二叉树的preorder嘛，s的下一层其实就是left，s的next其实就是right啊

请问楼主第二题对应lc上哪一道呀？

既然是dfs 那就不能用queue吧 写了一个iterative的方法 有没有老铁讨论一下这道题 不太懂recursive的方法

struct Node{
        int val;
        Node* next;
        Node* child;
}

class Iterator {
private:
        stack<Node*> nodes;
public:
        Iterator(Node* root){
                nodes.push(root);
        }
       
        int next(){
                Node* res = nodes.top();
                nodes.pop();
                if(res->next){
                        nodes.push(res->next);
                }
                return res->val;
        }
       
        bool hasNext(){
                while(!nodes.empty()){
                        Node* curr = nodes.top();
                        if(curr->child == NULL){
                                return true;
                        }
                        nodes.pop();
                        if(curr->next){
                                nodes.push(curr->next);
                        }
                        while(curr->child){
                                nodes.push(curr->child);
                                curr = curr->child;
                        }
                }
                return false;
        }
}

感谢分享 楼主加油