LeetCode: Binary Tree Level Order Traversal

C++

 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  */
10 class Solution {
11 public:
12     vector<vector<int>> levelOrder(TreeNode* root) {
13         vector<vector<int>> ans;
14         if (root == NULL) return ans;
15         vector<int> tmp;
16         queue<TreeNode *> que;
17         que.push(root);
18         que.push(NULL);
19         while (true) {
20             TreeNode *front = que.front();
21             que.pop();
22             if (front == NULL) {
23                 ans.push_back(tmp);
24                 if (que.empty() || que.front() == NULL) break;
25                 tmp.clear();
26                 que.push(NULL);
27             }
28             else {
29                 if (front->left) que.push(front->left);
30                 if (front->right) que.push(front->right);
31                 tmp.push_back(front->val);
32             }
33         }
34         return ans;
35     }
36 };

View Code

C#代码：

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public int val;
 5  *     public TreeNode left;
 6  *     public TreeNode right;
 7  *     public TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public List<List<int>> LevelOrder(TreeNode root) {
12         List<List<int>> ans = new List<List<int>>();
13         if (root == null) return ans;
14         List<int> tmp = new List<int>();
15         Queue<TreeNode> que = new Queue<TreeNode>();
16         que.Enqueue(root);
17         que.Enqueue(null);
18         while (true)
19         {
20             TreeNode peek = que.Peek();
21             que.Dequeue();
22             if (peek == null)
23             {
24                 ans.Add(tmp);
25                 if (que.Count == 0 || que.Peek() == null) break;
26                 tmp = new List<int>();
27                 que.Enqueue(null);
28             }
29             else {
30                 if (peek.left != null) que.Enqueue(peek.left);
31                 if (peek.right != null) que.Enqueue(peek.right);
32                 tmp.Add(peek.val);
33             }
34         }
35         return ans;
36     }
37 }

View Code