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,#,
#,15,7}
,
3 / 9 20 / 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
思路一:用两个vector分层次记录值,时间复杂度O(n),空间复杂度O(n)
1 /**
2 * Definition for binary tree
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 vector<vector<int> > levelOrder(TreeNode *root) {
13 vector<vector<int> > result;
14 if (root == nullptr) return result;
15
16 queue<TreeNode *> current, next;
17 vector<int> level;
18
19 current.push(root);
20 while (!current.empty()) {
21 while (!current.empty()) {
22 TreeNode *p = current.front();
23 current.pop();
24 level.push_back(p->val);
25 if (p->left != nullptr) next.push(p->left);
26 if (p->right != nullptr) next.push(p->right);
27 }
28 result.push_back(level);
29 level.clear();
30 swap(current, next);
31 }
32
33 return result;
34 }
35 };
思路二:BFS的思想。用一个queue,然后每次层结束时插入0到队列中。c
参考:https://leetcode.com/discuss/28762/c-solution-using-only-one-queue-use-a-marker-null
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 vector<vector<int> > levelOrder(TreeNode *root) { 13 vector<vector<int> > ret; 14 if (root == NULL) return ret; 15 16 vector<int> level; 17 queue<TreeNode *> q; 18 q.push(root); 19 q.push(0); 20 while (!q.empty()) { 21 TreeNode *p = q.front(); 22 q.pop(); 23 if (p) { 24 level.push_back(p->val); 25 if (p->left) 26 q.push(p->left); 27 if (p->right) 28 q.push(p->right); 29 } else { 30 ret.push_back(level); 31 level.clear(); 32 33 //当发现空指针时,要检查队列中是否还有节点 34 if (!q.empty()) 35 q.push(0); 36 } 37 } 38 39 return ret; 40 } 41 };