def levelOrder(self, root: TreeNode) -> List[int]:
if not root:
return []
queue = [root]
res = []
while queue:
size = len(queue)
for i in range(size):
cur = queue.pop(0)
res.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
return res
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int[] levelOrder(TreeNode root) {
if (root==null){
return new int[0];
}
List<Integer> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int size;
TreeNode node;
while (!queue.isEmpty()){
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);
}
res.add(node.val);
}
}
int[] arr = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
arr[i] = res.get(i);
}
return arr;
}
}
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
#对于每个节点，先入队列，然后出队列时将这个节点的左节点、右节点入队列。
if not root: return []
treedeque = collections.deque()
tree = []
treedeque.append(root)#先入队列
while treedeque:
tmp = treedeque.popleft()#然后出队列
tree.append(tmp.val)
if tmp.left:#出队列时入其左节点，右节点
treedeque.append(tmp.left)
if tmp.right:
treedeque.append(tmp.right)
return tree
class Solution {
public int[] levelOrder(TreeNode root) {
if (root == null) {
return new int[0];
}
List<Integer> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode p = queue.poll();
list.add(p.val);
if (p.left != null) {
queue.add(p.left);
}
if (p.right != null) {
queue.add(p.right);
}
}
return list.stream().mapToInt(Integer::intValue).toArray();
}
}
shuaidi
共以下 21 个回答
void printBinaryTree(TreeNode* root) {
if (root nullptr) {
return;
}
queue q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << ” “;
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
}//时间复杂度为 O(2^h),空间复杂度为 O(2^h)
使用层序遍历的思想 levelOrder(TreeNode root) { res;
/**
* 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
if (root nullptr) return res;
queue<TreeNode*> que; // 使用队列来存储当前层的节点
que.emplace(root); // 将根节点入队
while (!que.empty()) {
int size = que.size(); // 表示当前层的节点数量
for (int i = 1; i <= size; ++i) {
auto node = que.front();
que.pop();
res.emplace_back(node->val);
if (node->left) que.emplace(node->left);
if (node->right) que.emplace(node->right);
}
}
return res;
}
};
打卡
创建一个队列和数组， levelOrder(TreeNode* root) { res;//存储结果
队头等于root
后面循环，队列先进左再进右，存入数组res；
class Solution {
public:
vector
vector
if(!root )
return res;
queue <TreeNode*> q{{root}};
while(!q.empty())
{
auto t = q.front();
q.pop();
res.push_back(t->val);
if(t->left)
{
q.push(t->left);
}
if(t->right)
{
q.push(t->right);
};
时间On
时间复杂度：O(n) levelOrder(TreeNode root) { bfs;
/**
* 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
queue<TreeNode> q;
if(rootNULL) return {};
q.push(root);
while(!q.empty()){
TreeNode t = q.front();
bfs.push_back(t->val);
if(t->left!=NULL) q.push(t->left);
if(t->right!=NULL) q.push(t->right);
q.pop();
}
return bfs;
}
};
利用队列实现层序遍历
利用队列辅助
是时间复杂度ON，空间复杂度on
创建一个队列和数组，第一次用memest（指针；数值；大小（存储单位大小），
队头等于root
后面循环，队列先进左再进右，存入数组ans；
““#include<stido.h>
从上到下按层打印二叉树
int* levelOrder(struct TreeNode* root, int* returnSize) {
*returnSize = 0; // 初始化返回结果的大小为0
queue[tail++] = root; 这个语句将根节点的指针存储到队列数组 queue 中，而不是存储根节点的所有值。
while (head < tail) { // 当队列非空时循环
struct TreeNode* temp = queue[head++]; // 取出队首节点指针
}
時間複雜度 O(n) 空間複雜度 O(n)
用一個隊列來儲存要處理的node 再用另一個vector來儲存要打印的值
时间复杂度O(n);
空间复杂度O(n);
层序遍历
打卡
层序遍历
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
#对于每个节点，先入队列，然后出队列时将这个节点的左节点、右节点入队列。
if not root: return []
1、层次遍历
层序遍历
时间复杂度O(n)空间复杂度O(n)