二叉树的层序遍历无需递归？

Question

我正在尝试在 C++ 中不使用递归来实现二叉树的层序遍历。目标是从根开始逐层遍历树，并按正确的顺序打印节点。

我读到这可以使用队列来完成，但我在一些细节上遇到了困难：

如何初始化并使用 std::queue 来存储用于遍历的节点？ 将节点的左子节点和右子节点排队的正确方法是什么？ 如何确保处理完所有节点后循环停止？ 是否有我需要处理的边缘情况，例如一棵空树或一棵只有一个节点的树？

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

这是我的二叉树的基本结构：

我已经编写了一些代码，但它似乎无法正常工作，并且当我尝试访问子节点时，我不断遇到分段错误。有人可以解释实现此遍历的正确方法并帮助我理解可能出现的问题吗？

我尝试在 C++ 中使用 std::queue 实现级别顺序遍历。我的想法是将根节点入队，然后重复将前节点出队，处理其值，并将其左子节点和右子节点入队（如果存在）。

这是我尝试过的：

#include <iostream>
#include <queue>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void levelOrderTraversal(TreeNode* root) {
    std::queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();

        std::cout << current->val << " ";

        if (current->left != nullptr) {
            q.push(current->left);
        }
        if (current->right != nullptr) {
            q.push(current->right);
        }
    }
}

我希望这段代码能够打印树的层序遍历。

但是，我遇到了一些问题：

分段错误：当树为空时，或者尝试访问不存在的节点的当前->左或当前->右时，程序崩溃。 错误的输出：在某些情况下，遍历顺序不符合预期，我不确定我的队列操作是否正确。 我不知道如何有效地处理这些问题。我应该如何修改代码来处理空树等边缘情况或确保遍历顺序正确？任何指导将不胜感激！

Answer 1

现在你正试图阻止空指针被推入队列，并且当你遍历树时，依赖于你不会遇到任何空指针的事实。

不幸的是，这使得处理像空树这样的极端情况变得困难；你基本上必须确保根本不调用遍历函数。

我认为允许空指针进入队列更简单，但要确保遍历函数在遇到它们时不会出现错误行为。

void breadthFirstTraversal(TreeNode* root) {
    std::queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();

        if (current != nullptr) {
            std::cout << current->val << " ";
            q.push(current->left);
            q.push(current->right);
        }
    }
}

至少正如我所写的那样，这确实有一个缺点，即通过将空指针存储到队列中来使队列变得更大。如果这确实是一个问题，您可以像代码一样执行操作，并且仅在它们不为空时才推送它们。