我是靠谱客的博主 风中路灯,这篇文章主要介绍LeetCode:Binary Tree Level Order Traversal,现在分享给大家,希望可以做个参考。

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
8
3 / 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 Tags
  Tree Breadth-first Search
Hide Similar Problems
  (M) Binary Tree Zigzag Level Order Traversal (E) Binary Tree Level Order Traversal II (E) Minimum Depth of Binary Tree(M) Binary Tree Vertical Order Traversal

































思路:

层次遍历,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内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(109)

评论列表共有 0 条评论

立即
投稿
返回
顶部