从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
返回:
[3,9,20,15,7]
提示:
节点总数 <= 1000
方法一:copy
class Solution { public: vector<int> levelOrder(TreeNode* root) { vector<int> rest; queue<TreeNode*> q;//使用队列先进先出的特性,实现二叉树的广度优先搜索BFS if(!root) return rest; q.push(root);//根节点入队 while(!q.empty()) { TreeNode* node =q.front();//暂存队头元素 q.pop();//队头元素出队 rest.push_back(node->val); //若当前结点的左右子节点不为空,则先左后右将其子节点入队 if(node->left) q.push(node->left); if(node->right) q.push(node->right); } return rest; } };
从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
返回其层次遍历结果:
[ [3], [9,20], [15,7] ]
提示:
节点总数 <= 1000
方法一:copy
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { // 定义一个队列用来接收每一层 queue<TreeNode*> q; // 结果数组 vector<vector<int>> resVector; if (root == NULL) return resVector; q.push(root); while (!q.empty()) { vector<int> tempVector; for (int i = q.size(); i > 0; i--) { //这里的循环只会将队列q最初的长度值赋给i,所以后面入队的元素不影响 TreeNode* node = q.front(); q.pop(); tempVector.push_back(node->val); if (node->left != NULL) q.push(node->left); if (node->right != NULL) q.push(node->right); } resVector.push_back(tempVector); } return resVector; } };
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
返回其层次遍历结果:
[ [3], [20,9], [15,7] ]
提示:
节点总数 <= 1000
方法一:copy
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; if (root == nullptr) return res; deque<TreeNode*> dq; dq.push_back(root); int layer = 0; vector<vector<int>> ans; while (!dq.empty()) { auto size = dq.size(); vector<int> res; while (size--) { TreeNode* cur; if (layer & 1) { cur = dq.back(); dq.pop_back(); res.push_back(cur -> val); if (cur -> right) dq.push_front(cur -> right); if (cur -> left) dq.push_front(cur -> left); } else { cur = dq.front(); dq.pop_front(); res.push_back(cur -> val); if (cur -> left) dq.push_back(cur -> left); if (cur -> right) dq.push_back(cur -> right); } } ++layer; ans.push_back(res); } return ans; } };