?
Given binary tree {3,9,20,#,#,15,7},
?
? ? 3
? ?/ \
? 9 ?20
? ? / ?\
? ?15 ? 7
return its level order traversal as:
?
[
? [3],
? [9,20],
? [15,7]
]
思考了一下，居然被我想到了用队列来存储每一层的数据。嘿嘿。
?
用两个队列，一个队列用来输出，一个队列用来记录下一层的所有左右节点，然后循环使用两个队列即可。
?
复制代码
/**
?* Definition for binary tree
?* struct TreeNode {
?* ? ? int val;
?* ? ? TreeNode *left;
?* ? ? TreeNode *right;
?* ? ? TreeNode(int x) : val(x), left(NULL), right(NULL) {}
?* };
?*/
class Solution {
public:
? ? vector > levelOrder(TreeNode *root)?
? ? {
? ? ? ? vector > ans;
? ? ? ? if (!root) return ans;
? ? ? ??
? ? ? ? vector tmp;
? ? ? ? TreeNode *lf, *ri, *p;
? ? ? ? queue q1, q2;
? ? ? ? q1.push(root);
? ? ? ??
? ? ? ? while(!q1.empty() || !q2.empty())
? ? ? ? {
? ? ? ? ? ? while(!q1.empty())
? ? ? ? ? ? {
? ? ? ? ? ? ? ? p = q1.front();
? ? ? ? ? ? ? ? q1.pop();
? ? ? ? ? ? ? ? tmp.push_back(p -> val);
? ? ? ? ? ? ? ? if (p -> left)
? ? ? ? ? ? ? ? ? ? q2.push(p -> left);
? ? ? ? ? ? ? ? if (p -> right)
? ? ? ? ? ? ? ? ? ? q2.push(p -> right);
? ? ? ? ? ? }
? ? ? ? ? ? ans.push_back(tmp);
? ? ? ? ? ? tmp.clear();
? ? ? ? ? ? if (q1.empty() && q2.empty()) return ans; // q1完，判断是否都为空
?
? ? ? ? ? ? while(!q2.empty())
? ? ? ? ? ? {
? ? ? ? ? ? ? ? p = q2.front();
? ? ? ? ? ? ? ? q2.pop();
? ? ? ? ? ? ? ? tmp.push_back(p -> val);
? ? ? ? ? ? ? ? if (p -> left)
? ? ? ? ? ? ? ? ? ? q1.push(p -> left);
? ? ? ? ? ? ? ? if (p ->
right)
? ? ? ? ? ? ? ? ? ? q1.push(p -> right);
? ? ? ? ? ? }
? ? ? ? ? ? ans.push_back(tmp);
? ? ? ? ? ? tmp.clear();
? ? ? ? }
? ? ? ? return ans;
? ? }
};
复制代码
一开始使用两个flag标记，来判断是否进入了中间的两个while是否进入，用来判断是否要pushback。后面发现只要在上面注释部分判断是否都为空就行。
?
当然，我用到了两个队列。可不可以只用一个呢。
?
用一个队列的话就是用NULL来判断分层。每次完后输入一个NULL。例如：
?
复制代码
/**
?* Definition for binary tree
?* struct TreeNode {
?* ? ? int val;
?* ? ? TreeNode *left;
?* ? ? TreeNode *right;
?* ? ? TreeNode(int x) : val(x), left(NULL), right(NULL) {}
?* };
?*/
class Solution {
public:
? ? vector > levelOrder(TreeNode *root) {
? ? ? ? // IMPORTANT: Please reset any member data you declared, as
? ? ? ? // the same Solution instance will be reused for each test case.
? ? ? ? vector >res;
? ? ? ? if(root == NULL)return res;
? ? ? ? queue myqueue;
? ? ? ? myqueue.push(root);
? ? ? ? myqueue.push(NULL);//NULL是层与层之间间隔标志
? ? ? ? vector level;
? ? ? ? while(myqueue.empty() == false)
? ? ? ? {
? ? ? ? ? ? TreeNode *p = myqueue.front();
? ? ? ? ? ? myqueue.pop();
? ? ? ? ? ? if(p != NULL)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? level.push_back(p->val);
? ? ? ? ? ? ? ? if(p->left)myqueue.push(p->left);
? ? ? ? ? ? ? ? if(p->right)myqueue.push(p->right);
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? res.push_back(level);
? ? ? ? ? ? ? ? if(myqueue.empty() == false)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? level.clear();
? ? ? ? ? ? ? ? ? ? myqueue.push(NULL);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return res;
? ? }
};