Binary Tree Level Order Traversal

Question

Problem Statement

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},

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

return its level order traversal as:

  1. [
  2.   [3],
  3.   [9,20],
  4.   [15,7]
  5. ]

Challenge

Challenge 1: Using only 1 queue to implement it.

Challenge 2: Use DFS algorithm to do it.

題解 - 使用隊列

此題爲廣度優先搜索(BFS)的基礎題，使用一個隊列保存每層的節點即可。出隊列和將子節點入隊列的實現使用 for 循環，將每一輪的節點輸出。

C++

  1. /**
  2.  * Definition of TreeNode:
  3.  * class TreeNode {
  4.  * public:
  5.  *     int val;
  6.  *     TreeNode *left, *right;
  7.  *     TreeNode(int val) {
  8.  *         this->val = val;
  9.  *         this->left = this->right = NULL;
  10.  *     }
  11.  * }
  12.  */
  14. class Solution {
  15.     /**
  16.      * @param root: The root of binary tree.
  17.      * @return: Level order a list of lists of integer
  18.      */
  19. public:
  20.     vector<vector<int> > levelOrder(TreeNode *root) {
  21.         vector<vector<int> > result;
  23.         if (NULL == root) {
  24.             return result;
  25.         }
  27.         queue<TreeNode *> q;
  28.         q.push(root);
  29.         while (!q.empty()) {
  30.             vector<int> list;
  31.             int size = q.size(); // keep the queue size first
  32.             for (int i = 0; i != size; ++i) {
  33.                 TreeNode * node = q.front();
  34.                 q.pop();
  35.                 list.push_back(node->val);
  36.                 if (node->left) {
  37.                     q.push(node->left);
  38.                 }
  39.                 if (node->right) {
  40.                     q.push(node->right);
  41.                 }
  42.             }
  43.             result.push_back(list);
  44.         }
  46.         return result;
  47.     }
  48. };

Java

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.     public List<List<Integer>> levelOrder(TreeNode root) {
  12.         List<List<Integer>> result = new ArrayList<List<Integer>>();
  13.         if (root == null) return result;
  15.         Queue<TreeNode> q = new LinkedList<TreeNode>();
  16.         q.offer(root);
  17.         while (!q.isEmpty()) {
  18.             List<Integer> list = new ArrayList<Integer>();
  19.             int qSize = q.size();
  20.             for (int i = 0; i < qSize; i++) {
  21.                 TreeNode node = q.poll();
  22.                 list.add(node.val);
  23.                 // push child node into queue
  24.                 if (node.left != null) q.offer(node.left);
  25.                 if (node.right != null) q.offer(node.right);
  26.             }
  27.             result.add(new ArrayList<Integer>(list));
  28.         }
  30.         return result;
  31.     }
  32. }

源碼分析

  1. 異常，還是異常
  2. 使用STL的queue數據結構，將root添加進隊列
  3. 遍歷當前層所有節點，注意需要先保存隊列大小，因爲在入隊出隊時隊列大小會變化
  4. list保存每層節點的值，每次使用均要初始化

複雜度分析

使用輔助隊列，空間複雜度 O(n), 時間複雜度 O(n).