Binary Tree Level Order Traversal
最后更新于：2022-04-02 01:11:12
# Binary Tree Level Order Traversal
### Source
- lintcode: [(69) Binary Tree Level Order Traversal](http://www.lintcode.com/en/problem/binary-tree-level-order-traversal/)
~~~
Given a binary tree, return the level order traversal of its nodes' values.
(ie, from left to right, level by level).
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]
]
Challenge
Using only 1 queue to implement it.
~~~
### 题解 - 使用队列
此题为广搜的基础题，使用一个队列保存每层的节点即可。出队和将子节点入队的实现使用 for 循环，将每一轮的节点输出。
### C++
~~~
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public:
vector > levelOrder(TreeNode *root) {
vector > result;
if (NULL == root) {
return result;
}
queue q;
q.push(root);
while (!q.empty()) {
vector list;
int size = q.size(); // keep the queue size first
for (int i = 0; i != size; ++i) {
TreeNode * node = q.front();
q.pop();
list.push_back(node->val);
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
result.push_back(list);
}
return result;
}
};
~~~
### Java
~~~
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public ArrayList> levelOrder(TreeNode root) {
ArrayList> result = new ArrayList>();
if (root == null) return result;
Queue q = new LinkedList();
q.offer(root);
while (!q.isEmpty()) {
int qLen = q.size();
ArrayList aList = new ArrayList();
for (int i = 0; i < qLen; i++) {
TreeNode node = q.poll();
aList.add(node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
result.add(aList);
}
return result;
}
}
~~~
### 源码分析
1. 异常，还是异常
1. 使用STL的`queue`数据结构，将`root`添加进队列
1. **遍历当前层所有节点，注意需要先保存队列大小，因为在入队出队时队列大小会变化**
1. `list`保存每层节点的值，每次使用均要初始化
### 复杂度分析
使用辅助队列，空间复杂度 O(n)O(n)O(n), 时间复杂度 O(n)O(n)O(n).
';