层次遍历二叉树算法

层次遍历二叉树算法是一种广度优先搜索的算法，也称为BFS（Breadth-First Search）。它的主要思想是从二叉树的根节点开始，按照层次顺序依次遍历每个节点，先访问根节点，然后依次访问它的左右子节点，直到遍历完整个二叉树。

层次遍历二叉树算法可以使用队列来实现。首先将根节点入队，然后依次从队列中取出节点，访问该节点，并将其左右子节点入队，直到队列为空。

以下是层次遍历二叉树的示例代码：

void levelOrder(Node* root) {
    if (!root) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

其中，`Node`表示二叉树的节点，包含`val`、`left`和`right`三个成员变量，分别表示节点的值、左子节点和右子节点。函数`levelOrder`接受一个指向根节点的指针作为参数，按照层次顺序遍历整个二叉树，并输出每个节点的值。

相关问题

c++层次遍历二叉树算法

C++层次遍历二叉树算法是一种广度优先搜索（BFS）的算法，用于按层次顺序遍历二叉树的节点。以下是C++实现层次遍历二叉树的算法步骤：

1. 首先，创建一个队列（可以使用STL中的queue容器）来存储待访问的节点。
2. 将根节点入队。
3. 进入循环，直到队列为空：
- 从队列中取出一个节点，并访问该节点。
- 将该节点的左子节点和右子节点（如果存在）依次入队。
4. 重复步骤3，直到队列为空，即完成了层次遍历。

下面是一个示例代码实现：

#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) {
    if (root == nullptr) {
        return;
    }
    
    std::queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        
        std::cout << node->val << " ";
        
        if (node->left != nullptr) {
            q.push(node->left);
        }
        
        if (node->right != nullptr) {
            q.push(node->right);
        }
    }
}

int main() {
    // 构建二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    // 层次遍历二叉树
    levelOrderTraversal(root);
    
    return 0;
}

输出结果为：1 2 3 4 5，表示按层次顺序遍历二叉树的节点值。

层次遍历算法遍历二叉树

层次遍历算法是一种广度优先搜索算法，它按照层次的顺序遍历二叉树。具体实现方法是使用队列，首先将根节点入队，然后每次从队列中取出一个节点，访问该节点，并将其左右子节点（如果存在）入队，直到队列为空为止。下面是层次遍历算法遍历二叉树的Python实现：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root: TreeNode) -> List[List[int]]:
    if not root:
        return []
    res = []
    queue = [root]
    while queue:
        level = []
        for i in range(len(queue)):
            node = queue.pop(0)
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level)
    return res