解题思路

将根节点放到一个队列里面，再将其左节点、右节点依次放入队列里面。一个一个遍历节点。

• 先判断树为空的情况，返回空列表；
• 将根节点添加到待遍历数组内；
• 循环遍历节点，并将一层的节点遍历后的值放入一个数组内。

复杂度分析

时间复杂度和空间复杂度为O（N）。

代码

Python

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型二维数组
#
class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        res = []
        if root is None:
            return res
        
        tree_list = []
        tree_list.append(root)

        while len(tree_list) > 0:
            tmp = []
            for i in range(len(tree_list)):
                node = tree_list.pop(0)
                tmp.append(node.val)
                if node.left:
                    tree_list.append(node.left)
                if node.right:
                    tree_list.append(node.right)
            
            res.append(tmp)

        return res

C++

#include <queue>
#include <vector>
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.empty()) 
        {
            vector<int> tmp;
            int n = q.size();
            for(int i = 0; i < n; i++)
            {
                TreeNode* node = q.front();
                q.pop();

                tmp.push_back(node->val);
                if(node->left)
                {
                    q.push(node->left);
                }
                if(node->right)
                {
                    q.push(node->right);
                }
            }
            res.push_back(tmp);
        }
        return res;
    }
};