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

题目

解法

使用外部数据结构

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();
                que.pop();
                preNode->next = node;
                preNode = node;
            }
            if (node->left) {
                que.push(node->left);
            }
            if (node->right) {
                que.push(node->right);
            }
        }
        node->next = nullptr;
    }
    return root;
}

不使用外部数据结构-递归

void connectTwo(Node* node1, Node* node2) {
    if (node1 == nullptr || node2 == nullptr) {
        reutrn;
    }
    node1->next = node2;
    connectTwo(node1->left, node1->right);
    connectTwo(node2->left, node2->right);
    connectTwo(node1->right, node2->left);
}
Node* connect(Node* root) {
    if (root == nullptr) {
        return nullptr;
    }
    connectTwo(root->left, root->right):
    return root;
}

不使用外部数据结构-迭代

Node* connect(Node* root) {
    if (root == nullptr) {
        return nullptr;
    }
    Node* cur = root;
    while (cur->left != nullptr) {
        Node* pre = cur;
        while (pre != nullptr) {
            pre->left->next = pre->right;
            if (pre->next != nullptr) {
                pre->right->next = pre->next->left;
            }
            pre = pre->next;
        }
        cur = cur->left;
    }
    return root;
}