把二叉树打印成多行：广度优先的使用

最新推荐文章于 2021-10-27 20:21:18 发布

ifreewolf99

最新推荐文章于 2021-10-27 20:21:18 发布

阅读量114

点赞数

分类专栏：牛客网算法题文章标签：二叉树 bfs 算法

本文链接：https://blog.csdn.net/ifreewolf_csdn/article/details/108299927

版权

牛客网算法题专栏收录该内容

20 篇文章

订阅专栏

本文详细介绍了如何使用队列实现二叉树的层次遍历，包括标准的从上到下、从左至右的遍历，以及变体的之字形遍历。通过具体的代码示例，展示了BFS模板的运用。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

方法：队列

层次遍历打印二叉树，用队列实现。
BFS的模板为：

1.如果不需要确定当前遍历到了哪一层，模板如下：

void bfs() {
 vis[] = {0}; // or set
 queue<int> pq(start_val);
 
 while (!pq.empty()) {
     int cur = pq.front(); pq.pop();
     for (遍历cur所有的相邻节点nex) {
         if (nex节点有效 && vis[nex]==0){
             vis[nex] = 1;
             pq.push(nex)
         }
     } // end for
 } // end while
}

上述是伪代码，不仅可用于二叉树，可针对所有用BFS解题。

2.如果需要确定遍历到哪一层，模板如下；

void bfs() {
 int level = 0;
 vis[] = {0}; // or set
 queue<int> pq(original_val);
 while (!pq.empty()) {
     int sz = pq.size();
 
     while (sz--) {
             int cur = pq.front(); pq.pop();
         for (遍历cur所有的相邻节点nex) {
             if (nex节点有效 && vis[nex] == 0) {
                 vis[nex] = 1;
                 pq.push(nex)
             }
         } // end for
     } // end inner while
     level++;
 
 } // end outer while
}

所以此题可直接套用模板，代码如下：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int>> ret;
            if(pRoot == nullptr) return ret;
            
            queue<TreeNode *> q;
            q.push(pRoot);
            
            while(!q.empty()){
                int sz = q.size();
                vector<int> ans;
                while(sz--){
                    TreeNode *node = q.front();
                    q.pop();
                    ans.push_back(node->val);
                    
                    if(node->left) q.push(node->left);
                    if(node->right) q.push(node->right);
                }
                ret.push_back(ans);
            }
            return ret;
        }    
};

变体

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

只需要判断将偶数行反转就行了

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> ret;
        if(pRoot == nullptr) return ret;
        queue<TreeNode*> q;
        q.push(pRoot);
        
        int level = 0;
        while(!q.empty()){
            vector<int> ans;
            int sz = q.size();
            while(sz--){
                TreeNode *node = q.front();
                q.pop();
                ans.push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            ++level;
            if(!(level&1)) reverse(ans.begin(), ans.end());
            ret.push_back(ans);
        }
        return ret;
    }
    
};