二叉树分层遍历

首先定义二叉树的存储结构：

1 struct TreeNode {
2     int val;
3     TreeNode *left;
4     TreeNode *right;
5 
6     TreeNode(int v, TreeNode* l = NULL, TreeNode *r = NULL)
7         :val(v), left(l), right(r) {}
8 };

1.递归的方法（《编程之美》3.10）

　　二叉树本身就带有递归属性，通常我们可以用递归方法解决。假设要访问第k层节点，那么其实可以转皇城分别访问“以该二叉树根节点的左右子节点为根节点的两棵子树”中层次为k-1的节点。此方法需要求出二叉树的深度，其实可以直接访问到二叉树某一层次失败的时候返回就可以了。

　　这个方法的问题是递归调用，效率较低。而且对每一层的访问都需要从根节点开始，效率极差。

　　最坏的情况下（不平衡树）时间复杂度为O(n^2),空间复杂度O(1)

 1 //输出以root为根节点中的第level层中的所有节点（从左至右），成功返回1
 2 //失败返回0
 3 //root为二叉树根节点
 4 //level为层次数，其中根节点为第0层
 5 int PrintNodeAtLevel(TreeNode *root, int level) {
 6     if (!root || level < 0) return 0;
 7     if (level == 0){
 8         cout<<root->val;
 9         return 1;
10     }
11 
12     return PrintNodeAtLevel(root->left, level - 1) + PrintNodeAtLevel(root->right, level - 1);
13 }
14 
15 //层次遍历二叉树
16 //root，二叉树的根节点
17 void LevelOrder(TreeNode *root) {
18     for (int level = 0; ; level++) {
19         if (!PrintNodeAtLevel(root, level)) 
20             break;
21         cout<<endl;
22     }
23 }

2. 使用数组和两个游标的方法（《编程之美》 3.10）

　　在访问k层的时候，我们只需要知道k-1层的信息就足够了，所以在访问第k层的时候，要是能够知道k-1层的节点信息，就不再需要从根节点开始遍历了。

　　根据上述分析，可以从根节点出发，依次将每一层的根节点从左往右压入一个数组，并并用一个游标cur记录当前访问的节点，另一个游标last指示当前层次的最后一个节点的下一个位置，以cur===last作为当前层次访问结束的条件，在访问某一层的同时将该层的所有节点的子节点压入数组，在访问完某一层之后，检查是否还有新的层次可以访问，直到检查完所有的层次（不再有新的节点可以访问）

　　这种方法需要一个vector一直存储所有节点，空间效率较差。

　　时间复杂度为O(n),空间复杂度为O(n)

 1 void LevelOrder(TreeNode *root) {
 2     if (root == NULL) return;
 3     vector<TreeNode *> vec; //这里使用stl中的vector代替数组，可利用到
 4                             //其动态扩展的属性
 5     vec.push_back(root);
 6     int cur = 0, last = vec.size();
 7     while (cur < vec.size()) {
 8         last = vec.size();
 9 
10         while (cur < last) {
11             cout<<vec[cur]->val;
12             if (vec[cur]->left) 
13                 vec.push_back(vec[cur]->left);
14             if(vec[cur]->right)
15                 vec.push_back(vec[cur]->right);
16             ++cur;
17         }
18         cout<<endl;
19     }
20 }

3. 两个队列的方法

　　广度优先搜索的思想。使用两个队列，一个记录当前层的节点，另一个记录下一层的节点。输出当前层节点后交换，使下一层的节点称为当前层的节点。

　　时间复杂度O(n),空间复杂度O(1)

 1 void LevelOrder(TreeNode *root) {
 2     if (root == NULL) return ;
 3 
 4     queue<TreeNode *> current, next;
 5     
 6     current.push(root);
 7     while (!current.empty()) {
 8         while (!current.empty()) {
 9             TreeNode * p = current.front();
10             cout<<p->val<<" ";
11             current.pop();
12             if (p->left)
13                 next.push(p->left);
14             if (p->right)
15                 next.push(p->right);
16         }
17         cout<<endl;
18         swap(next, current);
19     }
20 }

4.使用一个队列和两个标记的方法

　　使用current记录当前节点的数量，nextlevel记录下一层节点的数量。当current==0时就将下一层置为当前层。

 1 void LevelOrder(TreeNode *root) {
 2     if (root == NULL) return;
 3 
 4     queue<TreeNode *> q;
 5     q.push(root);
 6     int nextlevel = 0; //记录下一层节点的数量
 7     int current = 1; //记录当前层节点的数量
 8 
 9     while (!q.empty()) {
10         TreeNode *p = q.front();
11         q.pop();
12         --current;
13         cout<<p->val<<" ";
14 
15         if (p->left) {
16             q.push(p->left);
17             ++nextlevel;
18         }
19         if (p->right) {
20             q.push(p->right);
21             ++nextlevel;
22         }
23 
24         if（current == 0) {
25             cout<<endl;
26             swap(current, nextlevel);
27         }
28     }
29 }

5. 使用一个队列加一个标记的方法

　　用队列暂存储节点，每当一层节点进入队列，就在最后加入一个空指针表示当前层结束。

 1 void LevelOrder(TreeNode *root) {
 2     if (root == NULL) return;
 3 
 4     queue<TreeNode *> q;
 5     q.push(root);
 6     q.push(0);
 7     while (!q.empty()) {
 8         TreeNode *p =q.front();
 9         q.pop();
10         if (p) {
11             cout<<p->val<<" ";
12             if (p->left)
13                 q.push(p->left);
14             if (p->right)
15                 q.push(p->right);
16             //当发现空指针（结束信号时），要检查队列是够还有节点
17             //如果没有的话还插入新的结束信号，则会造成死循环
18         } else if (!q.empty()) {
19             q.push(0);
20             cout<<endl;
21         }
22     }
23 }

参考资料：

　　　　　1.《编程之美》

　　　　　2. 《剑指offer》

　　　　　2. http://www.cnblogs.com/miloyip/archive/2010/05/12/binary_tree_traversal.html