117.填充每个节点的下一个右侧节点II

题目

解法

使用外部数据结构

可以使用队列来模拟层次遍历，每次先取出头节点，使用该节点连接后面的节点，再更新为下一个节点：

Node* connect(Node* root) {
    if (root == nullptr) {
        return nullptr;
    }
    queue<Node*> que;
    que.push(root);
    while (!que.empty()) {
        int len = que.size();
        Node* preNode, *node;
        for (int i = 0; i < len; ++i) {
            if (i == 0) {
                preNode = que.front();
                que.pop();
                node = preNode;
            } else {
                node = que.front();
                preNode->next = node;
                preNode = node;
            }
            if (node->left) {
                que.push(node->left);
            }
            if (node->right) {
                que.push(node->right);
            }
        }
        node->next = nullptr;
    }
    return root;
}

不使用外部数据结构

Node* connect(Node* root) {
    if (root == nullptr) {
        return nullptr;
    }
    // 建立一个节点作为每层链表的头节点
    Node* dummay = new Node(-1);
    Node* cur = root;
    while (cur != nullptr) {
        // 每层都是一个新的头节点，否则 pre 就不指向新的头节点
        dummay->next = nullptr;
        Node* pre = dummay;
        while (cur != nullptr) {
            if (cur->left) {
                pre->next = cur->left;
                pre = pre->next;
            }
            if (cur->right) {
                pre->next = cur->right;
                pre = pre->next;
            }
            cur = cur->next;
        }
        // 将虚拟头指针指向下一层
        cur = dummay->next;
    }
    reutrn root;
}