C++怎么解决每个节点的右向指针问题

在二叉树的相关问题中，有一种常见的问题是为每个节点设置一个指向其右侧节点的指针。这个问题通常出现在层次遍历的场景中，要求我们为每一层的节点设置一个指向同一层右侧节点的指针。本文将详细介绍如何使用C++解决这个问题，并探讨不同的实现方法及其优缺点。

问题描述

给定一个二叉树，假设每个节点都有一个next指针，指向其同一层的右侧节点。如果右侧没有节点，则next指针应设置为NULL。初始状态下，所有next指针都被设置为NULL。

例如，给定如下二叉树：

        1
       / \
      2   3
     / \   \
    4   5   7

填充next指针后，二叉树应变为：

        1 -> NULL
       / \
      2 -> 3 -> NULL
     / \   \
    4 ->5 ->7 -> NULL

解决方案

方法一：层次遍历（BFS）

层次遍历（BFS）是最直观的解决方法。我们可以使用队列来逐层遍历二叉树，并在遍历过程中为每个节点设置next指针。

实现步骤

1. 创建一个队列，并将根节点入队。
2. 当队列不为空时，进行以下操作：
   • 记录当前层的节点数量。
   • 遍历当前层的所有节点，并将它们的next指针指向队列中的下一个节点。
   • 将当前节点的左右子节点入队。
3. 重复上述步骤，直到队列为空。

代码实现

#include <queue>

struct Node {
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};

void connect(Node* root) {
    if (!root) return;

    std::queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();
        Node* prev = nullptr;

        for (int i = 0; i < size; ++i) {
            Node* curr = q.front();
            q.pop();

            if (prev) {
                prev->next = curr;
            }
            prev = curr;

            if (curr->left) q.push(curr->left);
            if (curr->right) q.push(curr->right);
        }
    }
}

复杂度分析

• 时间复杂度：O(N)，其中N是二叉树的节点数。每个节点只会被访问一次。
• 空间复杂度：O(M)，其中M是二叉树的最大宽度（即某一层的最大节点数）。在最坏情况下，队列中会存储一整层的节点。

方法二：使用已建立的next指针

在方法一中，我们使用了额外的队列空间来存储节点。为了优化空间复杂度，我们可以利用已经建立的next指针来进行层次遍历。

实现步骤

1. 从根节点开始，逐层遍历二叉树。
2. 对于每一层，使用一个指针curr从左到右遍历该层的所有节点。
3. 在遍历过程中，为每个节点的左右子节点设置next指针。
4. 移动到下一层，重复上述步骤。

代码实现

void connect(Node* root) {
    if (!root) return;

    Node* levelStart = root;

    while (levelStart) {
        Node* curr = levelStart;
        Node* prev = nullptr;

        while (curr) {
            if (curr->left) {
                if (prev) {
                    prev->next = curr->left;
                }
                prev = curr->left;
            }

            if (curr->right) {
                if (prev) {
                    prev->next = curr->right;
                }
                prev = curr->right;
            }

            curr = curr->next;
        }

        levelStart = levelStart->left;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中N是二叉树的节点数。每个节点只会被访问一次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

方法三：递归法

递归法是一种简洁的解决方案，但需要注意的是，递归法在处理每一层时需要额外的空间来存储递归栈。

实现步骤

1. 定义一个递归函数，该函数接受两个参数：当前节点和当前节点的next节点。
2. 在递归函数中，首先为当前节点设置next指针。
3. 递归处理当前节点的左子节点和右子节点。
4. 递归处理当前节点的next节点的左子节点和右子节点。

代码实现

void connect(Node* root) {
    if (!root) return;

    if (root->left) {
        root->left->next = root->right;
    }

    if (root->right && root->next) {
        root->right->next = root->next->left;
    }

    connect(root->left);
    connect(root->right);
}

复杂度分析

• 时间复杂度：O(N)，其中N是二叉树的节点数。每个节点只会被访问一次。
• 空间复杂度：O(H)，其中H是二叉树的高度。递归栈的深度取决于二叉树的高度。

总结

本文介绍了三种解决二叉树节点右向指针问题的方法：层次遍历（BFS）、使用已建立的next指针和递归法。每种方法都有其优缺点，具体选择哪种方法取决于问题的约束条件和实际需求。

• 层次遍历（BFS）：简单直观，但需要额外的队列空间。
• 使用已建立的next指针：空间复杂度最优，但实现稍复杂。
• 递归法：代码简洁，但递归栈可能占用较多空间。

在实际应用中，可以根据具体情况选择最合适的方法。如果空间复杂度是主要考虑因素，推荐使用第二种方法；如果代码简洁性是主要考虑因素，可以选择第三种方法。