二叉树BFS遍历

二叉树定义

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

一、层序遍历（使用队列）

使用一个队列贮存节点，如果根节点非空，将根节点入队。

只要队列非空，就循环，打印top节点，将左右子节点入队，pop队头。

vector<int> BiTree_order(TreeNode* root)
{
    vector<int> retvec;
    if (root == nullptr)
        return retvec;
    queue<TreeNode*> q;
    q.push(root);
    while (!empty(q))
    {
        auto t = q.front();
        q.pop();
        retvec.push_back(t->val);
        if (t->left != nullptr) q.push(t->left);
        if (t->right != nullptr) q.push(t->right);
    }
    return retvec;
}

二、层序遍历分层输出

如何界定每一层的分界点？

在每一层开始的时候获取队列长度，当前队列中的所有点都在同一层。

vector<int> BiTree_order(TreeNode* root)
{
    vector<vector<int>> retvec;
    if (root == nullptr)
        return retvec;
    queue<TreeNode*> q;
    auto t = root;
    q.push(root);
    while (!empty(q))
    {
        int size = q.size(); 
        vector<int> level;
        for (int i = 0; i < size; i++)
        {
            t = q.front();
            q.pop();
            level.push_back(t->val);
            if (t->left != nullptr) q.push(t->left);
            if (t->right != nullptr) q.push(t->right);

        }
        retvec.push_back(level);
    }
    return retvec;
}

二叉树BFS遍历

推荐阅读