Binary Tree Level Order Traversal
Total Accepted: 105297
Total Submissions: 318601
Difficulty: Easy
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}
,
复制代码
1
2
3
4
5
6
7
83 / 9 20 / 15 7
return its level order traversal as:
复制代码
1
2
3
4
5[ [3], [9,20], [15,7] ]
confused what "{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ.
Subscribe to see which companies asked this question
Hide Similar Problems
思路:
层次遍历,BFS。
新
java code:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> levelOrder(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); List<List<Integer>> ans = new LinkedList<List<Integer>>(); if(root == null) return ans; queue.offer(root); while(!queue.isEmpty()) { int size = queue.size(); List<Integer> subAns = new LinkedList<Integer>(); for(int i=0;i<size;i++) { TreeNode tmp = queue.poll(); subAns.add(tmp.val); if(tmp.left != null) queue.offer(tmp.left); if(tmp.right != null) queue.offer(tmp.right); } ans.add(subAns); } return ans; } }
c++ code:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ret; if(NULL == root) return ret; queue<TreeNode *> q[2]; stack<vector<int>> s; int cur=0; q[cur].push(root); while(!q[cur].empty()) { vector<int> tmp; while(!q[cur].empty()) { TreeNode *p = q[cur].front(); tmp.push_back(p->val); if(p->left) q[cur^1].push(p->left); if(p->right) q[cur^1].push(p->right); q[cur].pop(); } cur^=1; ret.push_back(tmp); } return ret; } };
最后
以上就是风中路灯最近收集整理的关于LeetCode:Binary Tree Level Order Traversal的全部内容,更多相关LeetCode:Binary内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复