【二叉树专题】剑指 Offer 32 – II. 从上到下打印二叉树-跟着帅地玩副业，开拓第二曲线PlayOffer

九号球普通 2023年11月15日下午11:11

“`java
与前一题一样，层序遍历，只是一层需要在一起
class Solution {
public List> decorateRecord(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List> res = new ArrayList<>();
Queue q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()) {
List list = new ArrayList<>();
int n = q.size();
for (int i = 0; i < n; i++) { TreeNode node = q.poll(); list.add(node.val); if (node.left != null) { q.add(node.left); } if (node.right != null) { q.add(node.right); } } res.add(list); } return res; } }

0 赞同 0 条回复

大大普通 2023年11月15日下午9:38

C++
 //就是高度的非递归求法
 //只用一个queue
class Solution {
public:
    vector<vector<int>> decorateRecord(TreeNode* root) {
       vector<vector<int>>ans;
       queue<TreeNode*>q;
       if(root==NULL)return ans;
       q.push(root);

      while(!q.empty()){
          vector<int>a;
        for(int i=q.size();i>0;i--){
            TreeNode* h=q.front();
            q.pop();
            a.push_back(h->val);
            if(h->left)q.push(h->left);
            if(h->right)q.push(h->right);
        }
        ans.push_back(a);
      }
      return ans;       
    }
};

0 赞同 0 条回复

招舟子普通 2023年8月26日下午12:21

“`java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List> levelOrder(TreeNode root) {
if(root==null){
return new ArrayList<>();
}
Queue queue = new LinkedList<>();
List> res = new ArrayList<>();
queue.offer(root);
while(!queue.isEmpty()){
int k = queue.size();
List pre = new ArrayList<>();
for(int i=0;i} return res; }

}
分层

0 赞同 0 条回复

jhfuture 普通 2023年8月11日下午10:23

“`java
有时间了慢慢补回来，加油！
public List> levelOrder(TreeNode root) {
if(root==null) return new ArrayList<>();

        Queue<TreeNode> queue = new LinkedList();
        List<List<Integer>> res= new ArrayList<>();
        queue.add(root);

        while(!queue.isEmpty()){
            // 里面有K 个则一层有k个
            int k= queue.size();
            // 边去取一层，边放入 。自己原本的思想是分开处理
            List tmp=new ArrayList<Integer>();
            for(int i=0;i<k;i++){
                TreeNode t=queue.poll();
                tmp.add(t.val);
              if(t.left!=null) queue.add(t.left);
              if(t.right!=null) queue.add(t.right);

            }
            // 循环接触则得到了一层
            res.add(tmp);
        }
        return res;
}

0 赞同 0 条回复

淡色花樱普通 2023年8月2日下午8:17

“`java
通过队列遍历每层的数据，然后加入到数组中
class Solution{
public List> levelOrder(TreeNode root){
if(root == null){
return new ArrayList<>();
}
Queue queue = new LinkedList<>();
List> res = new ArrayList<>();
queue.add(root);
while(!queue.isEmpty()){
int k = queue.size();
List tmp = new ArrayList<>();
for(int i =0;i

0 赞同 0 条回复

cute. 普通 2023年7月27日下午6:21

思路：相比于上一题需要多循环一层

var levelOrder = function(root) {
    if(root === null) return []
    const queue = [];
    const res = [];
    queue.push(root);
    while(queue.length > 0) {
        var t = queue.length;
        const tmp = []
        for(var i =0; i < t; i++) {
            const p = queue.shift();
            tmp.push(p.val);
            if(p.left !== null) queue.push(p.left);
            if(p.right !== null) queue.push(p.right);
        }
        res.push(tmp);
    }
    return res;
};

0 赞同 0 条回复

断舍离永久会员 2023年7月10日下午4:02

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        LinkedList<TreeNode> queue = new LinkedList();
        List<List<Integer>> result = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            //获得当前队列共有多少元素
            int k = queue.size();
            //存放该层元素的集合
            List<Integer> temp = new ArrayList<>();
            for(int i = 0; i < k; i++){
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
            //加入本层元素集合
            result.add(temp);
        }
        return result;
    }
}

0 赞同 0 条回复

CV大神普通 2023年7月10日上午9:30

 public List<List<Integer>> levelOrder(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> values = new ArrayList<>();
        if (root != null) {
            queue.addLast(root);
        }
        //画个图更好理解
        while (!queue.isEmpty()) {
            //当前层级的个数
            int currentLevelSize = queue.size();
            ArrayList<Integer> levelList = new ArrayList<>();
            for (int i = 0; i < currentLevelSize; i++) {
                TreeNode node = queue.pollFirst();
                levelList.add(node.val);
                if (node.left != null) {
                    queue.addLast(node.left);
                }
                if (node.right != null) {
                    queue.addLast(node.right);
                }
            }
            values.add(levelList);

        }
        return values;
    }

时间复杂度O(n)，空间复杂度O(n)

0 赞同 0 条回复

mpweixin用户普通 2023年7月8日下午5:24

C++实现

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> q;
        if(!root) return result;


        q.push(root);


        while(!q.empty()){

            vector<int> temp;

            for(int i = q.size();i > 0; i--){//控制层数
                TreeNode* node = q.front();
                q.pop();
                temp.push_back(node -> val);
                if(node -> left != nullptr){
                    q.push(node -> left);
                }
                if(node -> right != nullptr){
                    q.push(node -> right);
                }

            }

            result.push_back(temp);

        }
        return result;
    }
};

0 赞同 0 条回复

憨憨永久会员 2023年7月7日下午5:44

通过队列遍历每层的数据，然后加入到数组中

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null)return new ArrayList<>();
        List<List<Integer>> ans =new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int a=queue.size();
            TreeNode temp=null;
            List<Integer> arr=new ArrayList<>();
            for(int i=0;i<a;i++){
                temp=queue.poll();
                arr.add(temp.val);
                if(temp.left!=null){
                    queue.offer(temp.left);
                }
                if(temp.right!=null){
                    queue.offer(temp.right);
                }
            }
            ans.add(arr);
        }
        return ans;
    }
}

0 赞同 0 条回复

BOZ 普通 2023年7月7日下午12:55

【思路】利用C++ STL的queue库，在大循环的循环体中对每一层进行遍历，小循环的循环体中对每一层的每个节点进行遍历
【复杂度】时间/空间均为O(n)

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        std::queue<TreeNode*> q;
        vector<vector<int>> result;
        q.push(root);
        while(!q.empty()) {
            int level_size = q.size();
            std::vector<int> level_result;

            for(int k = 0;k < level_size; k++) {
                auto node = q.front();
                q.pop();
                if (node == NULL) continue;
                level_result.push_back(node->val);
                q.push(node->left);
                q.push(node->right);
            }
            if (!level_result.empty())
                result.push_back(level_result);
        }
        return result;
    }
};

0 赞同 0 条回复

Sexypig. 普通 2023年7月6日下午12:39

代码实现了对二叉树进行层次遍历，将每一层的节点值存储在一个独立的数组中，并将这些数组按层次顺序存储在最终结果的二维数组中。

思路：

这里使用了队列来辅助进行层次遍历。
首先判断根节点是否为空，若为空则返回空结果。
定义一个二维数组 ans 用于存储最终结果。
将根节点入队。
进入循环，直到队列为空。
在每次循环中，先获取当前层的节点个数 size，并创建一个一维数组 arr 用于存储当前层的节点值。
在内层循环中，将队首节点出队，并将其值存入 arr 中，同时将其左子节点和右子节点入队。
遍历完当前层的所有节点后，将 arr 存入最终结果数组 ans。
循环结束后，返回最终结果数组 ans。
这段代码可以输出一个二维数组，其中每个子数组代表二叉树的一层节点值。通过使用队列来辅助实现层次遍历，可以保证先遍历父节点，再遍历子节点，从而保证了层次遍历的顺序性。

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

// 定义二叉树的节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) return {}; // 如果根节点为空，则返回空结果

        vector<vector<int>> ans; // 用于存储结果的二维数组
        queue<TreeNode*> q; // 用于进行层次遍历的队列
        q.push(root); // 将根节点入队

        while (!q.empty()) { // 当队列不为空时，进行层次遍历
            int size = q.size(); // 获取当前层的节点个数
            vector<int> arr; // 用于存储当前层的节点值

            while (size > 0) {
                TreeNode* cur = q.front(); // 获取队首节点
                q.pop(); // 弹出队首节点
                arr.push_back(cur->val); // 将节点值存入当前层的结果数组

                if (cur->left) q.push(cur->left); // 如果有左子节点，则将左子节点入队
                if (cur->right) q.push(cur->right); // 如果有右子节点，则将右子节点入队

                --size; // 当前层的节点数减一
            }

            ans.push_back(arr); // 将当前层的结果数组存入最终结果数组
        }

        return ans; // 返回最终结果数组
    }
};

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月4日下午2:17

队列

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> list = new ArrayList<>();
        if(root==null)
            return list;
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> res = new ArrayList<>();
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode node = queue.poll();
                res.add(node.val);
                if(node.left!=null)
                    queue.offer(node.left);
                if(node.right!=null)
                    queue.offer(node.right);
            }
            list.add(res);
        }
        return list;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月4日上午10:38

java
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) {
            //return null;
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode tmp = root;
        q.add(root);
        while(!q.isEmpty()) {
            int k = q.size();
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < k; i++) {
                //把每一层的元素压入后取出就是一层
                tmp = q.poll();
                list.add(tmp.val);
                if(tmp.left != null) {
                    q.add(tmp.left);
                }
                if(tmp.right != null) {
                    q.add(tmp.right);
                }
            }
            res.add(list);
        }
        return res;
    }
}

时间和空间复杂度都是O(n)

0 赞同 0 条回复

局外人普通 2023年7月3日下午9:33

思路：采用层序遍历，同时根据队列辅助数据结构的特性（每层遍历完后，队列中便是下一层的元素），加入List
时间复杂度O(n) 空间复杂度O(n)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root==null)  return res;

        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        TreeNode rear = root;

        while(!queue.isEmpty()){
            int sz = queue.size();
            List<Integer> list = new LinkedList<>();

            for(int i=0; i<sz; i++){
                TreeNode cur = queue.poll();
                list.add(cur.val);

                if(cur.left!=null)  queue.offer(cur.left);
                if(cur.right!=null) queue.offer(cur.right);
            }
            res.add(list);
        }
        return res;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月3日下午6:27

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
if(!root)
{
    *returnSize=0;
    *returnColumnSizes=NULL;
    return NULL;
}
*returnSize=0;
int**res=(int**)malloc(sizeof(int*)*10000);
*returnColumnSizes=(int*)malloc(sizeof(int)*10000);
struct TreeNode**queue=(struct TreeNode**)malloc(sizeof(struct TreeNode*)*10000);
int head=0,rear=0;
queue[rear++]=root;
while(head<rear)
{
int preRear=rear;
res[*returnSize]=(int*)malloc(sizeof(int)*(preRear-head));
(*returnColumnSizes)[*returnSize]=preRear-head;
int index=0;
for(head=head;head<preRear;head++)
{
    struct TreeNode*tmp=queue[head];
    res[*returnSize][index++]=tmp->val;
    if(tmp->left) queue[rear++]=tmp->left;
    if(tmp->right) queue[rear++]=tmp->right;
}
(*returnSize)++;
}
 return res;
}

时间复杂度为O(n)
空间复杂度为O(n)

0 赞同 0 条回复

花老爷普通 2023年6月30日上午11:29

bfs
时间：O(n)
空间：O(n)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> subRes = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode temp = queue.poll();
                subRes.add(temp.val);
                if (temp.left != null) {
                    queue.offer(temp.left);
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                }
            }
            res.add(subRes);
        }
        return res;
    }
}

0 赞同 0 条回复

peach 普通 2023年6月29日下午12:05

思路

类似，层序遍历，每一层使用一个小list承接
时间复杂度O(n) 空间复杂度O(n)

代码

 //层序遍历，使用队列
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList();
        if(root == null) return res;
        int size;
        Deque<TreeNode> queue = new ArrayDeque();
        queue.addLast(root);
        while(!queue.isEmpty()){
            size = queue.size(); //每一层使用size标记，要进入小集合
            List<Integer> list = new ArrayList();
            while(size-- > 0){
                root = queue.removeFirst();
                list.add(root.val);
                if(root.left != null) queue.addLast(root.left);
                if(root.right != null) queue.addLast(root.right);
            }
            res.add(list); //遍历结束，把小集合加入大集合
        }
        return res;
    }
}

0 赞同 0 条回复

～普通 2023年6月29日上午11:32

class Solution {
public:
vector<vector> levelOrder(TreeNode* root) {
vector<vector> res;
queue<TreeNode> q;
if(rootnullptr){
return res;
}
q.push(root);
while(!q.empty()){
int sz = q.size();
vector ans;
for(int i=0;i<sz;i++){
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);
}
res.push_back(ans);
}
return res;
}
};
时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

mpweixin用户普通 2023年6月29日上午7:27

时间复杂度O(n)
空间复杂度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<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*>que;
        vector<vector<int> >res;
        if (!root) {
            return res;
        }
        que.push(root);
        while (!que.empty()) {
            int sz = que.size();
            vector<int>level;
            for (int i = 0; i < sz; i++) {
                TreeNode* curr = que.front();
                que.pop();
                level.push_back(curr->val);
                if (curr->left) {
                    que.push(curr->left);
                }
                if (curr->right) {
                    que.push(curr->right);
                }
            }
            res.push_back(level);
        }
        return res;
    }
};

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月29日上午6:14

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []

        if not root:
            return res

        queue = deque([root])

        while queue:

            cnt = len(queue)
            level = []

            for i in range(cnt):
                cur = queue.popleft()
                level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)

            res.append(level)

        return res

记录每一行的size

0 赞同 0 条回复

江畅普通 2023年6月28日下午11:32

// 从上到下打印二叉树
// 时间复杂度 O(N)
// 空间复杂度 O(N)
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }

        vector<vector<int>> res;
        queue<TreeNode*>    que;

        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            res.push_back(vector<int>());
            while (size--) {
                TreeNode* node = que.front();
                res.back().push_back(node->val);
                if (node->left != nullptr) {
                    que.push(node->left);
                }
                if (node->right != nullptr) {
                    que.push(node->right);
                }
                que.pop();
            }
        }
        return res;
    }
};

0 赞同 0 条回复

张君雅小妹妹普通 2023年6月28日下午9:47

思路：每层存一个list，通过遍历获得下一层。
时间复杂度：O(N)
额外空间复杂度：O(N)

执行用时：1 ms, 在所有 Java 提交中击败了78.43%的用户
内存消耗：41 MB, 在所有 Java 提交中击败了77.57%的用户

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return new ArrayList<>();
        // 存储第一层
        List<List<TreeNode>> tmpResList = new ArrayList<>();
        tmpResList.add(new ArrayList<>(){{
            add(root);
        }});
        // 从上一层遍历，放到下一层
        while(true){
            List<TreeNode> tmpRes = new ArrayList<>();
            for(TreeNode node : tmpResList.get(tmpResList.size() - 1)){
                if(node.left != null) tmpRes.add(node.left);
                if(node.right != null) tmpRes.add(node.right);
            }
            if(!tmpRes.isEmpty()){
                tmpResList.add(tmpRes);
            } else {
                break;
            }
        }

        // 将存储TreeNode的数组复制成存储Integer的数组
        List<List<Integer>> resLists = new ArrayList<>();
        for(List<TreeNode> nodeList : tmpResList){
            List<Integer> list = new ArrayList<>();
            for(TreeNode node : nodeList){
                list.add(node.val);
            }
            resLists.add(list);
        }

        return resLists;
    }
}

0 赞同 0 条回复

小吕普通 2023年6月27日下午10:22

c++层序遍历
比较简单
vector<vector> levelOrder(TreeNode* root) {
vector<vector>result;
if(rootNULL)return result;
queue<TreeNode>que;
que.push(root);
while(!que.empty())
{
vector temp;
TreeNode tempnode;
int len = que.size();
for(int i = 0;i<len;i++)
{
tempnode = que.front();
que.pop();
temp.push_back(tempnode->val);
if(tempnode->left!=NULL)que.push(tempnode->left);
if(tempnode->right!=NULL)que.push(tempnode->right);
}
result.push_back(temp);
}
return result;

0 赞同 0 条回复

屠龙手段普通 2023年6月27日下午8:19

节点和所在层数同时入队，通过数组下标添加节点值


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        queue = [[root, 0]]
        res = [[root.val]]
        while queue:
            cur_node = queue[0][0]
            level = queue[0][1]
            queue = queue[1:]
            if cur_node.left:
                res = self.update_res(cur_node.left.val, level + 1, res)
                queue.append([cur_node.left, level + 1])
            if cur_node.right:
                res = self.update_res(cur_node.right.val, level + 1, res)
                queue.append([cur_node.right, level + 1])
        return res

    def update_res(self, val, level, res):
        if level >= len(res):
            res.append([val])
        else:
            res[level].append(val)
        return res

0 赞同 0 条回复

张开怀普通 2023年6月27日下午6:46

class Solution{
public:
       vector<vector<int>> levelOrder(TreeNode* root) {
              vector<vector<int>> res;
              if(!root){
                     return res;
              }
              queue<TreeNode*> q{{root}};
              while (!q.empty()){
                     int n = q.size();
                     vector<int> level;
                     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;
       }
}

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

怀瑾永久会员 2023年6月27日下午5:34

C++实现

#include <iostream>
#include <queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void printLevelOrder(TreeNode* root) {
    if (root == NULL) // 判断二叉树是否为空
        return;

    queue<TreeNode*> q; // 定义队列存储节点
    q.push(root); // 将根节点入队

    while (!q.empty()) { // 只要队列不为空就继续循环
        int curLevelSize = q.size(); // 当前层节点数
        for (int i = 0; i < curLevelSize; i++) {
            TreeNode* curNode = q.front(); // 取出队首节点
            q.pop(); // 弹出队首节点

            cout << curNode->val << " "; // 打印节点值

            // 将当前节点的左右子节点入队
            if (curNode->left)
                q.push(curNode->left);
            if (curNode->right)
                q.push(curNode->right);
        }
        cout << endl; // 换行分隔
    }
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);

    printLevelOrder(root); // 打印输出结果

    return 0;
}

0 赞同 0 条回复

彦，，# 普通 2023年6月27日下午4:32

vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root) return {};
         vector<vector<int>> res;
         /* 定义一个队列用于存储节点的数据 */
        queue<TreeNode*> q;
        if(root != nullptr) q.push(root);
        while(!q.empty())
        {
            vector<int> vv;
            int n = q.size();
            for(int i =0;i<n;i++)
            {
                TreeNode* temp = q.front();
                q.pop();
                vv.push_back(temp->val);
                if(temp->left != nullptr) q.push(temp->left);
                if(temp->right != nullptr) q.push(temp->right);
            }
            res.push_back(vv);
        }
        return res;

0 赞同 0 条回复

普通 2023年6月27日下午4:32

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<>();
       if(root != null) que.add(root);
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        TreeNode front = null;
        while(!que.isEmpty()){
            TreeNode index =  que.poll();
            if(front == null){
                que.add(null);
            }
            front = index;
            if(index == null){
                if(!list.isEmpty()){
                    resultList.add(list);
                }
                list = new ArrayList<>();
                continue;
            }
            list.add(index.val);
            if(index.left != null){
                que.add(index.left);
            }
            if(index.right != null){
                que.add(index.right);
            }
        }
        return resultList;
    }

层序遍历，利用队列NULL值隔离每层元素
时间复杂度O(n)

0 赞同 0 条回复

大鑫啊普通 2023年6月27日下午2:09

时空复杂度O(n)
1、每一层都用一个列表进行保存，
2、队列不为空时遍历，遍历当前队列中每个元素，每出队列一个元素，就把其入临时列表存储，将它的左右孩子入队列
3、每一层遍历结束，将临时列表加入返回列表中

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null)return new ArrayList();
        Queue<TreeNode> queue = new LinkedList();
        List<List<Integer>> res = new ArrayList();
        queue.offer(root);
        while(!queue.isEmpty()){
            int k = queue.size();
            List<Integer> tmp = new ArrayList();
            for(int i=0;i<k;i++){
                TreeNode t = queue.poll();
                tmp.add(t.val);
                if(t.left != null)queue.offer(t.left);
                if(t.right != null)queue.offer(t.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

0 赞同 0 条回复

Vow the vow。普通 2023年6月27日上午11:46

要分别记录每一层的值，因此需要获得每一层的节点数。

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);
        while(!queue.isEmpty()){
            int m = queue.size();
            List<Integer> list = new ArrayList<>();
            while(m-- > 0){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(new ArrayList<>(list));
        }
        return res;
    }

0 赞同 0 条回复

désire. 普通 2023年6月27日上午9:19

C++实现
class Solution {
public:
vector<vector> levelOrder(TreeNode* root) {
vector<vector> res;
res.clear();
if(root NULL) return res;
queue<TreeNode> que;
que.push(root);
while(!que.empty())
{
int size = que.size();
vector vec;
for(int i = 0;i < size;i++)
{
TreeNode node = que.front();
int value = que.front()->val;
vec.push_back(value);
que.pop();
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
res.push_back(vec);
}
return res;
}
};

0 赞同 0 条回复

硬核洋葱普通 2023年6月26日下午10:34

/**
 * 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<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> treeque;
        vector<vector<int>> ans;
        if(!root)   return ans;

        treeque.push(root);
        vector<int> layerans;
        TreeNode* lastnode = root, *nextlastnode;
        while(!treeque.empty()){
            TreeNode* node = treeque.front();
            treeque.pop();
            layerans.push_back(node->val);

            if(node->left){
                treeque.push(node->left);
                nextlastnode = node->left;
            }
            if(node->right){
                treeque.push(node->right);
                nextlastnode = node->right;
            }

            if(lastnode == node){
                ans.push_back(layerans);
                layerans = {};
                lastnode = nextlastnode;
            }
        }

        return ans;
    }
};

标记层中的最后一个节点，第一层的最后一个节点显然是 root
在遍历本层的时候，标记下一层最后的那个节点。到了本层最后一个节点，就把本层向量并入答案向量
这个做法时间复杂度O(n) 空间复杂度O(n)
看了下面的做法，发现队列中的节点数（队列仅含某一层节点时）可以作为遍历条件，比这个方法要好…

0 赞同 0 条回复

橙子陈普通 2023年6月26日下午10:13

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (null == root){
            return new ArrayList<>();
        }

Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    List<List<Integer>> res = new ArrayList<>();
    while(!queue.isEmpty()){
        int k = queue.size();

        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            TreeNode t = queue.poll();
            ans.add(t.val);
            if (null != t.left) queue.add(t.left);
            if (null != t.right) queue.add(t.right);
        }
        res.add(ans);
    }
    return res;
   }
}

时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

Jerry 普通 2023年6月26日下午10:10

 //BFS + 队列
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> orders = new ArrayList<>();
        if(root != null) queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> order = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) { //倒序
                TreeNode node = queue.poll();
                order.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            orders.add(order);
        }
        return orders;
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

伏月三十普通 2023年6月26日下午9:34

法1

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();
        if(root==null){
            return result;
        }

        LinkedList<TreeNode> queue=new LinkedList<>();

        queue.add(root);
        int c1=1;//上一层的节点数(是根节点)
        while(!queue.isEmpty()){
            List<Integer> res=new ArrayList<>();
            int c2=0;//当前层的节点数
            for(int i=0;i<c1;i++){
                TreeNode poll=queue.poll();
                res.add(poll.val);
                if(poll.left!=null){
                    queue.add(poll.left);
                    c2++;
                }
                if(poll.right!=null){
                    queue.add(poll.right);
                    c2++;
                }
            }
            c1=c2;
            result.add(res);
        }
        return result;
    }
}

法2：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();
        if(root==null){
            return result;
        }

        LinkedList<TreeNode> queue=new LinkedList<>();

        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> res=new ArrayList<>();
            int k=queue.size();
            for(int i=0;i<k;i++){
                TreeNode poll=queue.poll();
                res.add(poll.val);
                if(poll.left!=null){
                    queue.add(poll.left);
                }
                if(poll.right!=null){
                    queue.add(poll.right);
                }
            }
            result.add(res);
        }
        return result;
    }
}

上面两种方法的时间复杂度和空间复杂度都是O(n)

0 赞同 0 条回复

行动派小彩笔普通 2023年6月26日下午9:15

 //时间复杂度O(n),空间复杂度O(n)
 // 层次遍历，把每层的数据保留在vector中
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root) return {};
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty())
        {

            vector<int> v;
            for(int i = q.size();i>0;--i)
            {
                TreeNode* tmp = q.front();
                q.pop();
                v.push_back(tmp->val);
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
            }
            ans.push_back(v);
        }
        return ans;
    }
    vector<vector<int>> ans;
};

0 赞同 0 条回复

yxy 普通 2023年6月26日下午8:48

/**
 * 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<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size())
        {
            int n=q.size();
            vector<int> vec;
            while(n--)
            {
                auto cur=q.front();
                q.pop();
                vec.push_back(cur->val);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            res.push_back(vec);
        }
        return res;
    }
};

复杂度O（n）

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月26日下午6:57

//时间O(n) 空间O(n)
public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList();
        }

        List<List<Integer>> result = new ArrayList();
        Queue<TreeNode> queue = new LinkedList();

        queue.offer(root);
        while(!queue.isEmpty()){
            int curSize = queue.size();
            List<Integer> curLayer = new ArrayList();

            for(int i = 0;i < curSize;i++){
                root = queue.poll();    
                curLayer.add(root.val);
                if(root.left != null){
                    queue.offer(root.left);
                }
                if(root.right != null){
                    queue.offer(root.right);
                }
            }

            result.add(curLayer);
        }

        return result;
    }

0 赞同 0 条回复

Ming 普通 2023年6月26日下午6:21

复杂度O(n) O(n)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList();
        if(root == null) return list;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()) {
            int k = q.size();
            List<Integer> tmp = new ArrayList<>();
            for(int i = 0; i < k; i++) {
                TreeNode node = q.poll();
                tmp.add(node.val);
                if(node.left != null) {
                    q.offer(node.left);
                }
                if(node.right != null) {
                  q.offer(node.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }
}

0 赞同 0 条回复

残月冷骄阳普通 2023年6月26日下午5:00

复杂度

时间复杂度: $O(n)$
空间复杂度: $O(n)$

Code

/**
 * 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>> lists = new ArrayList<List<Integer>>();
        if (root == null){
            return lists;
        }
        ArrayDeque<TreeNode> nodes = new ArrayDeque<>();
        nodes.offer(root);
        while (!nodes.isEmpty()){
            LinkedList<Integer> res = new LinkedList<>();
            int size = nodes.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = nodes.poll();
                res.add(cur.val);
                if (cur.left != null){
                    nodes.offer(cur.left);
                }
                if (cur.right != null) {
                    nodes.offer(cur.right);
                }
            }
            lists.add(res);
        }
        return lists;
    }
}

0 赞同 0 条回复

Dsjh 普通 2023年6月26日下午4:43

// c++ 队列
class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root){
            return ans;
        }
        deque<TreeNode*> q;
        q.push_back(root);
        while(!q.empty()){
            int num = q.size();
            vector<int> temp;
            while(num--){
                TreeNode* t = q.front();
                temp.push_back(t->val);
                q.pop_front();
                if(t->left) q.push_back(t->left);
                if(t->right) q.push_back(t->right);
            }
            ans.push_back(temp);
        }
        return ans;
    }
};

0 赞同 0 条回复

雨落圆荷普通 2023年6月26日下午3:38

class Solution {
public List<List> levelOrder(TreeNode root) {
if(root null){
return new ArrayList<>();
}

    Queue<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();

    queue.add(root);
    while(!queue.isEmpty()){
        int k = queue.size();
        List<Integer> tmp = new ArrayList<>();
        for(int i = 0; i < k; i++){
            TreeNode t = queue.poll();
            tmp.add(t.val);
            if(t.left != null) queue.add(t.left);
            if(t.right != null) queue.add(t.right);
        }
        res.add(tmp);
    }

    return res;
}

}
时间复杂度：O(n)
额外空间复杂度：容器里最对存放 1/2 的节点，故为 O(n)

0 赞同 0 条回复

Yodl. 普通 2023年6月26日下午3:08

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(root == NULL)     return ans;
        queue<TreeNode*> myQue;
        myQue.push(root);
        while(!myQue.empty()){
            vector<int> tmp;
            int size = myQue.size();
            for(;size--;myQue.pop()){
                TreeNode* node = myQue.front();
                if(node->left)      myQue.push(node->left);
                if(node->right)     myQue.push(node->right);               
                tmp.push_back(node->val);
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};
//时间复杂度O(n)  空间复杂度O(n)

0 赞同 0 条回复

【二叉树专题】剑指 Offer 32 – II. 从上到下打印二叉树

共以下 44 个回答

思路

代码

复杂度

Code

# 回答此问题取消回复

【二叉树专题】剑指 Offer 32 – II. 从上到下打印二叉树

共以下 44 个回答

思路

代码

复杂度

Code

# 回答此问题 取消回复

# 回答此问题取消回复