102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example: Given binary tree [3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

return its level order traversal as:

[ [3], [9,20], [15,7] ]

题意： 给定一个二叉树，返回层次遍历的结果。结果为一个二维数组，每层的结点保存在一个数组中。

思路： 同BFS实现层次遍历，关键在于如何分层处理——在while(!q.empty())内加一层循环，以q的size为循环长度，每次循环处理删除一个q中的结点。这样在内存循环结束时，q中保存的就都是下一层的结点。

8ms

class Solution { public: vector<vector<int> > levelOrder(TreeNode *root) { vector<vector<int> > res; if (root == NULL) return res; queue<TreeNode*> q; q.push(root); while (!q.empty()) { vector<int> oneLevel; //保存每层的结果 int size = q.size(); for (int i = 0; i < size; ++i) { TreeNode *node = q.front(); q.pop(); oneLevel.push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } res.push_back(oneLevel); } return res; } };

此外，这道题还有递归的解法。核心在于需要一个二维数组，和一个变量level，当level递归到上一层的个数，新建一个空层，继续往里面加数字。可以想象为从左到右按列依次填充res的内容：

8ms

class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int> > res; levelorder(root, 0, res); return res; } void levelorder(TreeNode *root, int level, vector<vector<int> > &res) { if (!root) return; if (res.size() == level) res.push_back({}); //如果递归的层数达到level，则在res中新建一个空层 res[level].push_back(root->val); if (root->left) levelorder(root->left, level + 1, res); if (root->right) levelorder(root->right, level + 1, res); } };