题面

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

层序遍历二叉树,要求从上到下,从左到右,输出结果为二维vector。

样例

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]
]

算法

想法:还记得怎么进行层序遍历吗?结果是一个一维数组。现在的情景是要把每一层用一个单独的vector存起来,仅此而已。那么我们的首要问题就是,怎么解决“一层”的问题。

其实,我们在处理完上一层时,queue中就会只包含有本层的节点指针,那么我们计算queue.size(),然后只处理queue的前queue.size()个元素不就可以了吗?在处理其中每一个元素的时候,判空。非空的话,值压入vector,然后把左孩子和有孩子都再次压入queue,最后queue.pop()。处理完这一层,就把当前vector整个压入结果vector<vector<int>> res 中。

1. 根节点判空,若空,返回空vector<vector<int>> (); 不空,继续

2. 新建queue<TreeNode*> q, 和结果vector<vector<int>> res,根节点压入q中

3. 若q非空,while循环判断

新建vector。计算q元素个数,即为一层节点,逐个判空,若不空,值压入vector。然后把子节点压入q中,然后把它弹出queue。

处理完这层,若vector不空,整个压入res中。

4. 返回 res 结束。

源码

1 /**
2  * Definition for a binary tree node.
3  * struct TreeNode {
4  *     int val;
5  *     TreeNode *left;
6  *     TreeNode *right;
7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8  * };
9  */
 1 class Solution {
 2 public:
 3     vector<vector<int>> levelOrder(TreeNode* root) {
 4         //层序遍历
 5         if(root == nullptr)
 6             return vector<vector<int>> ();
 7         
 8         vector<vector<int>> res;
 9         queue<TreeNode*> q;
10         q.push(root);
11         while(!q.empty())
12         {
13             int size = q.size();
14             vector<int> tmp;
15             while(size--)
16             {
17                 TreeNode* p = q.front();
18                 if(p != nullptr)
19                 {
20                     tmp.push_back(p->val);
21                     q.push(p->left);
22                     q.push(p->right);
23                 }
24                 q.pop();
25             }
26             if(tmp.size() != 0)
27                 res.push_back(tmp);
28         }
29         return res;
30     }
31 };