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. */
  13. class Solution {
  14. /**
  15. * @param root: The root of binary tree.
  16. * @return: Level order a list of lists of integer
  17. */
  18. public:
  19. vector<vector<int> > levelOrder(TreeNode *root) {
  20. vector<vector<int> > result;
  21. if (NULL == root) {
  22. return result;
  23. }
  24. queue<TreeNode *> q;
  25. q.push(root);
  26. while (!q.empty()) {
  27. vector<int> list;
  28. int size = q.size(); // keep the queue size first
  29. for (int i = 0; i != size; ++i) {
  30. TreeNode * node = q.front();
  31. q.pop();
  32. list.push_back(node->val);
  33. if (node->left) {
  34. q.push(node->left);
  35. }
  36. if (node->right) {
  37. q.push(node->right);
  38. }
  39. }
  40. result.push_back(list);
  41. }
  42. return result;
  43. }
  44. };

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;
  14. Queue<TreeNode> q = new LinkedList<TreeNode>();
  15. q.offer(root);
  16. while (!q.isEmpty()) {
  17. List<Integer> list = new ArrayList<Integer>();
  18. int qSize = q.size();
  19. for (int i = 0; i < qSize; i++) {
  20. TreeNode node = q.poll();
  21. list.add(node.val);
  22. // push child node into queue
  23. if (node.left != null) q.offer(node.left);
  24. if (node.right != null) q.offer(node.right);
  25. }
  26. result.add(new ArrayList<Integer>(list));
  27. }
  28. return result;
  29. }
  30. }

源碼分析

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

複雜度分析

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