C++ 中每个节点的下一个右侧指针填充

2025 年 2 月 11 日 | 阅读 13 分钟

在二叉树的每个节点中填充下一个右侧指针是一个经典的计算机科学问题，它涉及增强树的结构以方便某些类型的遍历和操作。当需要进行逐层操作时，这个问题尤其相关，例如在广度优先搜索 (BFS) 中，我们需要一起处理同一级别的节点。

在许多与树相关的算法和应用中，节点必须逐层遍历或连接，以便每个节点都可以直接访问同一级别的右邻节点。这在广度优先搜索 (BFS)、层序遍历以及各种图算法等场景中特别有用。

填充二叉树中每个节点的下一个右侧指针的问题涉及为每个节点添加一个名为 next 的指针。这个 next 指针应该指向当前节点同一级别上紧邻的右侧节点。如果不存在这样的节点，则 next 指针应设置为 nullptr。

这项任务在计算机网络中有实际应用，其中同一级别的节点可能代表需要相互通信的设备或服务器。它也用于图形用户界面，其中同一级别的元素需要链接起来以便高效导航。

方法一：使用队列的层序遍历

在层序遍历中，节点从左到右逐层访问。通过使用队列，我们可以保持遍历树时节点的顺序。在每个级别，我们将每个节点的 next 指针设置为队列中紧跟其后的节点。此过程一直持续到当前级别的所有节点都处理完毕。

使用队列进行层序遍历是解决在二叉树的每个节点中填充下一个右侧指针问题的直接方法。此方法利用广度优先搜索 (BFS) 技术逐层遍历树，确保同一级别的所有节点都通过其 next 指针连接起来。以下是在 C++ 中的详细解释和实现。

程序

 
#include <iostream>
#include <queue>
using namespace std;
// Definition for a Node in the binary tree
struct Node {
    int val;
    Node* left;
    Node* right;
    Node* next;
    // Constructor to initialize Node with given value and null pointers
    Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}
};
class Solution {
public:
    //Function to connect next right pointers using level order traversal
    Node* connect(Node* root) {
        if (!root) return nullptr; // Return if tree is empty
        queue<Node*> q; // Queue to store nodes for level order traversal
        q.push(root); // Enqueue root node
        while (!q.empty()) {
            int levelSize = q.size(); // Number of nodes at current level
            for (int i = 0; i < levelSize; ++i) {
                Node* node = q.front(); // Get front node in the queue
                q.pop(); // Dequeue current node
                if (i < levelSize - 1) {
                    node->next = q.front(); // Set next pointer to the next node in the queue
                }
                // Enqueue left and right children if they exist
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
        }
        return root; // Return the modified root of the binary tree
    }
};
//Function to print the next pointers of the binary tree nodes
void printNextPointers(Node* root) {
    cout << "Next pointers in the binary tree:" << endl;
    Node* levelStart = root; // Start with the root node of the binary tree
    while (levelStart) {
        Node* node = levelStart; // Start with the leftmost node at the current level
        while (node) {
            cout << node->val;
            if (node->next) {
                cout << " -> ";
            } else {
                cout << " -> nullptr";
            }
            node = node->next; // Move to the next node in the same level
        }
        cout << endl;
        // Move to the leftmost node of the next level
        levelStart = levelStart->left ? levelStart->left : levelStart->right;
    }
}
// Helper function to create a binary tree with given values
Node* createBinaryTree(vector<int>& values, int index) {
    if (index >= values.size() || values[index] == -1) {
        return nullptr;
    }
    Node* root = new Node(values[index]);
    root->left = createBinaryTree(values, 2 * index + 1);
    root->right = createBinaryTree(values, 2 * index + 2);
    return root;
}
//Function to delete the binary tree nodes (post-order traversal)
void deleteBinaryTree(Node* root) {
    if (!root) return;
    deleteBinaryTree(root->left);
    deleteBinaryTree(root->right);
    delete root;
}
int main() {
    // Example usage: Create a binary tree manually
    vector<int> values = {1, 2, 3, 4, 5, 6, 7};
    Node* root = createBinaryTree(values, 0);
    // Create an object of Solution class
    Solution solution;
    // Connect next right pointers in the binary tree
    Node* connectedRoot = solution.connect(root);
    // Print the next pointers in the binary tree
    printNextPointers(connectedRoot);
    // Clean up allocated memory (not necessary in some environments)
    // In a real application, use proper memory management techniques
    deleteBinaryTree(root);
    return 0;
}   

输出

 
Next pointers in the binary tree:
1 -> nullptr
2 -> 3 -> nullptr
4 -> 5 -> 6 -> 7 -> nullptr

说明

任务是修改二叉树，使得每个节点的 next 指针指向同一级别的直接右侧节点。这允许逐层高效地遍历树，从而促进层序遍历或其他需要同一级别节点间连接的算法。

节点结构
Node 结构是我们二叉树表示的基础构建块。它封装了以下属性：
Val：表示节点中存储的数据的整数值。
Left：指向左子节点的指针。
Right：指向右子节点的指针。
Next：指向同一级别下一个节点的指针，初始设置为 nullptr。
此结构使我们能够构建一个二叉树，其中每个节点都可以通过 next 指针潜在地指向其直接右邻节点。
解决方案类和方法
Solution 类包含了使用名为 connect 的方法连接这些下一个右侧指针的算法逻辑。以下是该方法如何实现其目标的详细介绍：
队列初始化和层序遍历
为了有效地进行层序遍历，我们使用一个 std::queue<Node*> 命名为 q。这个队列有助于在树从上到下、从左到右遍历时保持节点的顺序。
Enqueue 根节点：首先将树的根节点入队到队列 q 中。
处理每个级别
只要队列 q 不为空，算法就继续执行以下步骤：
访问队列的大小，以确定当前级别（levelSize）的节点数。对当前级别的每个节点进行迭代（最多 levelSize 次）。
从队列中出队队首节点，该节点代表当前正在处理的节点。
如果当前节点不是其级别的最后一个节点 (i < levelSize - 1)，则将其 next 指针设置为指向队列中的下一个节点。这会在同一级别内建立下一个右侧指针关系。
将当前节点的任何存在的左子节点和右子节点入队到队列 q，以确保它们在后续迭代中被处理。
遍历完成：此过程将一直持续到所有节点都出队并处理完毕。此时，二叉树内的所有下一个右侧指针都应根据层序遍历正确设置。
打印下一个指针
printNextPointers 函数负责直观地验证 connect 方法的结果。它逐层遍历二叉树，从每个级别的最左侧节点开始。
初始化：以一个指向二叉树根节点的指针 levelStart 开始。
迭代打印：在遍历每个级别时：
从当前级别的最左侧节点 (node) 开始。
打印每个节点的 قيمة，后跟一个箭头 (->) 表示其下一个指针。
继续遍历下一个指针，直到到达当前级别的末尾。
将 levelStart 更新为下一个级别的最左侧节点 (levelStart = levelStart->left ? levelStart->left : levelStart->right)。
此函数清晰地可视化了在应用 connect 方法后，节点如何通过其下一个指针连接。
主函数
main 函数是执行和测试二叉树连接逻辑的入口点。
二叉树创建：使用一个表示节点值的整数向量 (values) 来构建二叉树。该树使用 createBinaryTree 函数递归构建，该函数根据提供的数值动态分配节点。
解决方案执行：创建 Solution 类的实例 (solution)，以将 connect 方法应用于二叉树的根节点。
验证和输出：连接下一个右侧指针后，调用 printNextPointers 函数来显示结果。这可以验证 connect 方法是否已正确链接了跨级别的节点。
内存清理：通过调用 deleteBinaryTree 函数来演示正确的内存管理，该函数递归删除二叉树所有动态分配的节点，以防止内存泄漏。

复杂度分析

时间复杂度

提供的解决方案中的主要方法是 connect，它使用队列通过广度优先搜索 (BFS) 方法逐层遍历二叉树并建立下一个指针。以下是时间复杂度的详细分解：

遍历节点

二叉树中的每个节点都入队一次，出队一次。

因此，对于一个有 n 个节点的二叉树，入队和出队操作的次数是 n。

内部循环执行

在二叉树的每个级别，我们处理该级别存在的所有节点。所有级别的节点数之和等于树中的总节点数 n。

设置 next 指针并入队其子节点（如果存在）是每个节点的常数时间操作。由于入队和出队都是 O(1) 操作，并且每个节点都只执行这些操作一次，因此处理所有节点的总体时间复杂度为 O(n)。

空间复杂度

解决方案的空间复杂度由在任何给定时间用于在队列中存储节点的最多空间决定。以下是详细分析：

队列空间

队列逐层存储节点。在任何级别中队列中存储的节点数最多对应于二叉树的最大宽度。

在最坏情况下，对于一个完全平衡的二叉树，最后一个级别（叶子节点）的最大节点数约为 n/2。

最大宽度

对于高度为 h 的平衡二叉树，最后一个级别包含多达 2^h 个节点。

给定高度为 h 的二叉树对于平衡树是 log(n)（基数为 2），在最坏情况下的最大宽度是：然而，对于大多数实际场景来说，这是一个过于悲观的估计。通常，对于平衡二叉树，队列所需的空间与叶子节点的数量成正比，即 O(n/2) = O(n)。

辅助空间

除了队列使用的空间外，该算法还使用固定量的额外空间用于 levelSize 和循环计数器等变量。

考虑到存储平衡树中最多 n/2 个节点到队列中的最坏情况，以及辅助变量使用的固定空间，总体空间复杂度为 O(n)。

方法二：恒定空间迭代方法

填充二叉树中每个节点的下一个右侧指针的恒定空间迭代方法是一种高效的方法，它避免使用额外的空间，如队列或其他数据结构，来达到相同的目标。此方法利用二叉树的现有结构及其 next 指针来逐层遍历和连接节点。

在二叉树中，每个节点最多可以有两个子节点：一个左子节点和一个右子节点。任务是连接每个节点与同一级别内的直接右邻节点，为每个级别形成一个链表状结构。这通常通过层序遍历来实现，其中节点从左到右逐层处理。

程序

 
#include <iostream>
// Definition for a Node in the binary tree
struct Node {
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}
};
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return nullptr; // Return if the tree is empty
        Node* current = root; // Start with the root of the tree
        while (current) {
            Node* dummy = new Node(0); // Dummy node to help with next level connections
            Node* tail = dummy; // Tail pointer to build the next level connections
            // Traverse the current level
            while (current) {
                if (current->left) {
                    tail->next = current->left; // Connect tail to current's left child
                    tail = tail->next; // Move the tail pointer
                }
                if (current->right) {
                    tail->next = current->right; // Connect tail to current's right child
                    tail = tail->next; // Move the tail pointer
                }
                current = current->next; // Move to the next node in the current level
            }
            current = dummy->next; // Move to the next level
            delete dummy; // Clean up the dummy node
        }
        return root; // Return the modified root of the binary tree
    }
};
//Function to print the next pointers of the binary tree nodes
void printNextPointers(Node* root) {
    std::cout << "Next pointers in the binary tree:" << std::endl;
    Node* levelStart = root; // Start with the root node of the binary tree
    while (levelStart) {
        Node* node = levelStart; // Start with the leftmost node at the current level
        while (node) {
            std::cout << node->val;
            if (node->next) {
                std::cout << " -> ";
            } else {
                std::cout << " -> nullptr";
            }
            node = node->next; // Move to the next node in the same level
        }
        std::cout << std::endl;
        // Move to the leftmost node of the next level
        levelStart = levelStart->left ? levelStart->left : levelStart->right;
    }
}
int main() {
    // Example usage: Create a binary tree manually
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    // Create an object of the Solution class
    Solution solution;
    // Connect next right pointers in the binary tree
    Node* connectedRoot = solution.connect(root);
    // Print the next pointers in the binary tree
    printNextPointers(connectedRoot);
    // Clean up allocated memory (not necessary in some environments)
    delete root->left->left;
    delete root->left->right;
    delete root->right->left;
    delete root->right->right;
    delete root->left;
    delete root->right;
    delete root;
    return 0;
}

输出

 
Next pointers in the binary tree:
1 -> nullptr
2 -> 3 -> nullptr
4 -> 5 -> 6 -> 7 -> nullptr

说明

提供的代码旨在连接二叉树中每个节点的 next 指针，使每个节点指向同一级别内的直接右邻节点。这是使用恒定空间迭代方法实现的，避免了像队列这样的额外空间。

节点结构
Node 结构定义了二叉树中每个节点的结构，包括其值 (val)、指向其左子节点和右子节点 (left, right) 的指针，以及一个初始化为 nullptr 的 next 指针。
解决方案类
Solution 类包含 connect 方法：它从根节点开始。使用一个虚拟节点和一个尾部指针来管理下一级别的连接。外部 while 循环遍历级别，而内部 while 循环遍历当前级别的节点。
对于每个节点，使用尾部指针连接其左子节点和右子节点。当前指针使用 next 指针移动到同一级别的下一个节点。处理完一个级别后，通过 dummy->next 将当前指针更新为下一级别的最左侧节点。
打印下一个指针
printNextPointers 函数逐层遍历树，从根节点开始，并打印每个节点的 قيمة，后跟其 next 指针。
主函数
main 函数手动构建二叉树，使用 connect 方法连接下一个右侧指针，打印连接的下一个指针，最后清理分配的内存。
总而言之，代码有效地利用了现有的树结构和 next 指针来连接二叉树跨级别的节点，确保了具有恒定空间复杂度的有效遍历。

复杂度分析

时间复杂度

提供的解决方案中的主要方法是 connect，它使用恒定空间迭代方法逐层遍历二叉树并建立下一个指针。以下是时间复杂度的详细分解：

遍历节点

二叉树中的每个节点都被访问一次。对于一个包含 n 个节点的二叉树，每个节点以 O(1) 的常数时间进行处理，以设置 next 指针并将它们移动到下一个节点或级别。因此，遍历涉及访问 n 个节点。

内部循环执行

对于二叉树的每个级别，我们处理该级别存在的所有节点。所有级别的节点数之和等于树中的总节点数 n。对于每个节点，设置 next 指针和移动指针是常数时间操作。

由于每个节点的遍历和指针设置都是 O(1) 操作，并且每个节点都只执行这些操作一次，因此处理所有节点的总体时间复杂度为 O(n)。

空间复杂度

解决方案的空间复杂度由算法所需的最多额外空间决定。以下是详细分析：

虚拟节点和尾部指针

该算法使用一个虚拟节点和一个尾部指针来管理下一级别的连接。这些指针不依赖于树的大小，因此其空间使用是恒定的 O(1)。

当前指针

当前指针用于遍历当前级别的节点。与虚拟节点和尾部指针一样，此指针也独立于树的大小，因此空间使用是恒定的 O(1)。

无额外数据结构

与使用队列或其他数据结构的方法不同，此方法不需要额外的节点存储空间。因此，它避免了与此类数据结构相关的 O(n) 空间复杂度。

辅助空间

除了虚拟节点、尾部指针和当前指针使用的空间外，该算法还为循环计数器等辅助变量使用固定量的额外空间。考虑到所有这些因素，总体空间复杂度为 O(1)。

下一个主题C++ 中的贝塞尔插值

← 上一个下一个 →

C++ 中每个节点的下一个右侧指针填充

方法一：使用队列的层序遍历

程序

说明

复杂度分析

方法二：恒定空间迭代方法

程序

说明

复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中每个节点的下一个右侧指针填充

方法一：使用队列的层序遍历

程序

说明

复杂度分析

方法二：恒定空间迭代方法

程序

说明

复杂度分析

相关帖子

C++17 功能和增强

C++ 中的超图实现

C++ 代码查找哈希冲突的索引

C++ 中查找旋转排序数组的枢轴

C++ 中使用 Pell 数查找

C++ 中的 std::defer_lock_t、std::try_to_lock_t 和 std::adopt_lock_t

C++ 中的皮尔逊相关系数

C++ 中的订婚数

C++ std::strong_ordering

C++ 中的等分数字

订阅 Tpoint Tech

联系信息