C++如何实现每个节点的右向指针

在二叉树中，每个节点通常包含一个指向左子节点和右子节点的指针。然而，在某些情况下，我们可能需要为每个节点添加一个额外的指针，指向同一层中右侧的节点。这种结构通常被称为“完美二叉树”或“完全二叉树”，并且这种指针被称为“右向指针”或“下一个指针”。本文将详细介绍如何在C++中实现每个节点的右向指针。

1. 问题描述

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
    int val;
    Node* left;
    Node* right;
    Node* next;
};

我们需要填充每个节点的 next 指针，使其指向其右侧的节点。如果右侧没有节点，则 next 指针应设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

2. 解决方案

2.1 层序遍历法

层序遍历（BFS）是一种常见的解决二叉树问题的方法。我们可以使用队列来实现层序遍历，并在遍历过程中为每个节点设置 next 指针。

2.1.1 算法步骤

1. 创建一个队列，并将根节点入队。
2. 当队列不为空时，进行以下操作：
   • 记录当前层的节点数量 size。
   • 遍历当前层的所有节点：
     • 将队首节点出队。
     • 如果当前节点不是当前层的最后一个节点，则将其 next 指针指向队首节点。
     • 将当前节点的左子节点和右子节点入队。
3. 重复步骤2，直到队列为空。

2.1.2 代码实现

#include <queue>

using namespace std;

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return nullptr;
        
        queue<Node*> q;
        q.push(root);
        
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                Node* node = q.front();
                q.pop();
                
                if (i < size - 1) {
                    node->next = q.front();
                }
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        
        return root;
    }
};

2.1.3 复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树中的节点数量。我们需要遍历每个节点一次。
• 空间复杂度：O(N)，在最坏情况下，队列中需要存储二叉树中一层的所有节点。

2.2 使用已建立的 next 指针

在完美二叉树中，我们可以利用已经建立的 next 指针来避免使用额外的空间。具体来说，我们可以通过遍历每一层的节点，并使用 next 指针来连接下一层的节点。

2.2.1 算法步骤

1. 从根节点开始，遍历每一层的节点。
2. 对于每一层的节点，使用 next 指针来连接下一层的节点。
3. 重复步骤2，直到遍历完所有层。

2.2.2 代码实现

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return nullptr;
        
        Node* leftmost = root;
        
        while (leftmost->left) {
            Node* head = leftmost;
            
            while (head) {
                // 连接左子节点和右子节点
                head->left->next = head->right;
                
                // 连接右子节点和下一个节点的左子节点
                if (head->next) {
                    head->right->next = head->next->left;
                }
                
                // 移动到下一个节点
                head = head->next;
            }
            
            // 移动到下一层
            leftmost = leftmost->left;
        }
        
        return root;
    }
};

2.2.3 复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树中的节点数量。我们需要遍历每个节点一次。
• 空间复杂度：O(1)，我们只使用了常数级别的额外空间。

2.3 递归法

递归是另一种解决二叉树问题的常见方法。我们可以通过递归遍历二叉树的每一层，并在遍历过程中为每个节点设置 next 指针。

2.3.1 算法步骤

1. 如果当前节点为空，则返回。
2. 如果当前节点的左子节点不为空，则将其 next 指针指向右子节点。
3. 如果当前节点的 next 指针不为空，则将其右子节点的 next 指针指向 next 节点的左子节点。
4. 递归处理左子节点和右子节点。

2.3.2 代码实现

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return nullptr;
        
        if (root->left) {
            root->left->next = root->right;
            if (root->next) {
                root->right->next = root->next->left;
            }
        }
        
        connect(root->left);
        connect(root->right);
        
        return root;
    }
};

2.3.3 复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树中的节点数量。我们需要遍历每个节点一次。
• 空间复杂度：O(log N)，递归调用栈的深度等于二叉树的高度。

3. 总结

本文介绍了三种在C++中实现每个节点的右向指针的方法：层序遍历法、使用已建立的 next 指针和递归法。每种方法都有其优缺点，具体选择哪种方法取决于具体的应用场景和需求。

• 层序遍历法：简单直观，但需要额外的空间来存储队列。
• 使用已建立的 next 指针：空间复杂度最优，但需要理解如何利用已建立的 next 指针。
• 递归法：代码简洁，但递归调用栈可能会占用较多的空间。

在实际应用中，可以根据具体情况选择最合适的方法。