# 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).