LeetCode --- 102. Binary Tree Level Order Traversal

題目連結：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).

For 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] 
] 
           

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

1 
  / \ 
 2   3 
    / 
   4 
    \ 
     5 
           

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

這道題的要求是分層周遊二叉樹。

由于需要把每層的節點分别放入到數組中，是以需要引入變量n記錄每層的節點數量。剩下的，就是廣度優先搜尋的方法了。

廣度優先搜尋算法（Breadth First Search），又叫寬度優先搜尋，或橫向優先搜尋。從根節點開始，沿着樹的寬度周遊樹的節點。如果所有節點均被通路，則算法中止。借助隊列資料結構，由于隊列是先進先出的順序，是以可以先将左子樹入隊，然後再将右子樹入隊。這樣一來，左子樹結點就存在隊頭，可以先被通路到。

時間複雜度：O(n)

空間複雜度：O(n)

1 class Solution {
 2 public:
 3     vector<vector<int> > levelOrder(TreeNode *root)
 4     {
 5         vector<vector<int> > vvi;
 6         
 7         if(NULL == root)
 8             return vvi;
 9         
10         queue<TreeNode *> q;
11         q.push(root);
12         while(!q.empty())
13         {
14             vector<int> vi;
15             for(int i = 0, n = q.size(); i < n; ++ i)
16             {
17                 TreeNode *temp = q.front();
18                 q.pop();
19                 if(temp -> left != NULL)
20                     q.push(temp -> left);
21                 if(temp -> right != NULL)
22                     q.push(temp -> right);
23                 vi.push_back(temp -> val);
24             }
25             vvi.push_back(vi);
26         }
27         
28         return vvi;
29     }
30 };
           

轉載請說明出處：LeetCode --- 102. Binary Tree Level Order Traversal