# 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<vector<int> > levelOrder(TreeNode *root) { vector<vector<int> > result; if (NULL == root) { return result; } queue<TreeNode *> q; q.push(root); while (!q.empty()) { vector<int> 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<ArrayList<Integer>> levelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if (root == null) return result; Queue<TreeNode> q = new LinkedList<TreeNode>(); q.offer(root); while (!q.isEmpty()) { int qLen = q.size(); ArrayList<Integer> aList = new ArrayList<Integer>(); 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).