二叉树的层次遍历（分层输出） |
您所在的位置：网站首页 › 层次遍历的顺序 › 二叉树的层次遍历（分层输出） |
二叉树的层次遍历（分层输出）
|
题目描述 给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历） 例如： 给定的二叉树是{3,9,20,#,#,15,7} 分析 二叉树的层次遍历可以用 BFS 来实现，使用一个队列 queue 来实现要区分每一层节点的个数，可以考虑每次访问时，访问同一层的所有元素，将下一层的所有元素放入队列（使用 size 函数来计算一层节点数）程序设计 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: vector levelOrder(TreeNode* root) { // write code here vector res; queue q; if (root == NULL) return res; q.push(root); vector v; while(!q.empty()){ v.clear(); // 将同一层的节点全部出队 int size = q.size(); while (size--){ TreeNode* temp = q.front(); v.push_back(temp->val); if (temp->left) q.push(temp->left); // 下一层所有节点入队 if (temp->right) q.push(temp->right); q.pop(); } res.push_back(v); // 存储当前层的节点输出 } return res; } }; |
该二叉树层序遍历的结果是【本文地址】
今日新闻 |
推荐新闻 |