class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
queue = [root]
res = []
while queue:
size = len(queue)
tmp = []
for i in range(size):
cur = queue.pop(0)
tmp.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
res.append(tmp)
return res
class Solution {
public:
vector> levelOrder(TreeNode* root) {
vector> res;
if (root == NULL) {
return res;
}
queue q;
q.push(root);
while(!q.empty()) {
int q_size = q.size();
vector level; //record the values of current layer
//for loop for traversing each layer from left to right
for (int i = 0; i < q_size; i++) {
TreeNode* curr = q.front();
q.pop();
level.push_back(curr->val);
if (curr->left != NULL)
q.push(curr->left);
if (curr->right != NULL)
q.push(curr->right);
}
res.push_back(level);
}
return res;
}
};
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if root is None:return []
queue = collections.deque()
tree = []
queue.append(root)
while queue:
tmp = []
for _ in range(len(queue)):
node = queue.popleft()
tmp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
tree.append(tmp)
return tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root==null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int size;
TreeNode node;
while (!queue.isEmpty()){
List<Integer> list = new ArrayList<>();
size=queue.size();
for (int i = 0; i < size; i++) {
node=queue.poll();
if (node.left!=null){
queue.add(node.left);
}
if (node.right!=null){
queue.add(node.right);
}
list.add(node.val);
}
res.add(list);
}
return res;
}
}
shuaidi
共以下 21 个回答
// 后序遍历二叉搜索树
void postorderTraversal(TreeNode* root) {
if (root NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf(“%d “, root->val);
}//时间负载O（n），空间复杂度O（n）
//使用层序> levelOrder(TreeNode *root) > res; q{{root}}; level(n);
//使用二维数组存储最终结果 用一维数组存储单层的结果
//使用队列存储数据
//记录 每层的层数 先将头指针的数据存入 然后将其提取出来 再将左右指针的值存入对列 层数加一 备份队列的数据 不让丢失
class Solution()
{
public:
vector<vector
{
vector<vector
if(rootNULL)
return res;
queue
while(!q.empty)
{
int n = q.size();
vector
for(int i=0;i<n;i++)
{
auto t = q.front();
q.pop();
level.push_back(t->val);
if(t->left)
{
q.push(t->left);
}
if(t->right)
{
q.push(t->right);
}
}
res.push_back(level);
}
return res;
}
};
/**> levelOrder(TreeNode root) {> res; cur; // 存储当前层的节点
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// 采用层序遍历的方法遍历
vector<vector
vector<vector
if (root nullptr) return res;
queue<TreeNode*> que; // 使用队列来存储当前层的节点
que.emplace(root); // 将根节点入队
while (!que.empty()) {
int size = que.size(); // 表示当前层的节点数量
vector
for (int i = 1; i <= size; ++i) {
auto node = que.front();
que.pop();
cur.emplace_back(node->val);
if (node->left) que.emplace(node->left);
if (node->right) que.emplace(node->right);
}
// 将当前层的节点加入到数组中
res.emplace_back(cur);
}
return res;
}
};
时间复杂度：O(n)> levelOrder(TreeNode root) {> bfs; vals; t = q.front();
空间复杂度：O(n)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector
vector<vector
queue<TreeNode> q;
if(rootNULL) return {};
q.push(root);
while(!q.empty()){
vector
int n=q.size();
for(int i=0;i<n;i++){
TreeNode
vals.push_back(t->val);
if(t->left!=NULL) q.push(t->left);
if(t->right!=NULL) q.push(t->right);
q.pop();
}
bfs.push_back(vals);
}
return bfs;
}
};
打卡
时间On
利用辅助记长，来在while内部实现小循环
类似于32-|
时间on空间on
和上一题差不多，加了2为数组，和for循环来判断每层装哪些元素；
““““c
#define MAX_SIZE 10000
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
*returnSize = 0; // 初始化返回结果的大小为0
}
// 这段代码实现了从上到下按层打印二叉树，并将每一层的节点值保存在一个二维数组中，同时返回每一层的节点个数。
// 首先，对于特殊情况，如果根节点为空，函数将返回空指针，并将返回数组的大小 returnSize 设置为0。
// 然后，我们使用一个队列来进行BFS（广度优先搜索）。定义一个大小为 MAXSIZE 的队列 queue，并初始化头指针 head 和尾指针 tail 都为0。
// 接下来，我们动态分配内存给返回的二维数组 res 和用于存储每一层节点个数的一维数组 *returnColumnSizes。这里使用 malloc 函数进行内存分配，所以在调用该函数之后记得在合适的时候释放内存。
// 然后，将根节点加入队列 queue 中，表示第一层的节点。并将 returnSize 初始化为0。
// 在循环中，使用队列的大小 size 来遍历当前层的所有节点。首先，将 size 存入 returnColumnSizes 数组中，表示当前层的节点个数。然后，为当前层的节点值分配内存，并将节点值保存到 res 数组中。
// 接着，通过出队操作（queue[head++]）将当前层的节点从队列中取出，并将其值存储到 res 数组中相应的位置。
// 同时，如果当前节点存在左子节点，则将左子节点加入队列中；如果当前节点存在右子节点，则将右子节点加入队列中。这样可以保证下一层的节点按从左到右的顺序加入队列。
// 最后，在循环结束后，将 returnSize 增加1，表示已经遍历完一层。最终，函数返回保存节点值的二维数组 res。
時間複雜度 O(n) 空間複雜度 O(n)
利用每一層的節點數 來逐個將該層節點值加入答案vector中儲存
算法流程思考：
第一步，梳理题目解题步骤或者解题条件，比如本题解题的两个个条件是：
1. 按层打印；
2. 每层打印到一行。
第二步，为每一个解题条件提供对应的解题思路：
对于1，又称为二叉树的 广度优先搜索（BFS）。BFS 通常借助 队列 的先入先出特性来实现。
对于2， 将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。通过每一层的队列长度来控制。
第三步，思考算法流程：
首先，处理特例情况（为空）以及初始化；
其次，有循环则先考虑循环的跳出条件（我们的两个解题条件都需要循环）：
外部循环——BFS循环跳出条件：当queue为空时跳出；
循环内步骤：
新建一个临时表tmp，存储本层临时打印结果；
内部循环——在BFS中，每层的循环跳出条件：当层的queue的元素全部pop（），即队列长度为0，通过range(len(queue))来控制。
循环步骤：
出队；
打印；
添加子节点
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if root is None:return []
queue = collections.deque()
tree = []
时间复杂度O(n)，空间复杂度O(n)
打卡
1、层次遍历。保存每层的节点个数
层序遍历