binary tree: level order traversal

二叉树的层次遍历，总结 5 种方式：
1. use two queues
使用两个 queue 表示当前层和下一层，一边遍历当前层 (current queue) 的时候，一边把 child nodes 加入到下一层 (next queue) 中；
遍历完当前层之后，把 next queue 置换到 current queue，清空 next queue，然后继上一段遍历逻辑。

1. void levelOrder(Node *root) {
   
2.     if (!root) return;
   
3.     queue<Node*> currentLevel, nextLevel;
   
4.     currentLevel.push(root);
   
5.     while (!currentLevel.empty()) {
   
6.         Node *currNode = currentLevel.front();
   
7.         currentLevel.pop();
   
8.         if (currNode != nullptr) {
   
9.             cout << currNode->data << " ";
   
10.             nextLevel.push(currNode->left);
    
11.             nextLevel.push(currNode->right);
    
12.         }
    
13.         if (currentLevel.empty()) {
    
14.             cout << endl;
    
15.             swap(currentLevel, nextLevel);
    
16.         }
    
17.     }
    
18. }

复制代码

2. use an extra variable to save the next level count of nodes
原理同上，只不过这次是用两个 int 变量来记录当前层和下一层要遍历的元素数量。

1. void leverOrder() {
   
2.     queue<Node*> q;
   
3.     q.push(this->root);
   
4.     int cur = 1, next = 0;
   
5.     while(!q.empty()) {
   
6.         Node *tmp = q.front();
   
7.         q.pop();
   
8.         --cur;
   
9.         if (tmp != nullptr) {
   
10.             cout << tmp->item << " ";
    
11.             q.push(tmp->left);
    
12.             q.push(tmp->right);
    
13.             next += 2;
    
14.         }
    
15.         if(cur == 0) {
    
16.             cout << endl;
    
17.             cur = next;
    
18.             next = 0;;
    
19.         }
    
20.     }
    
21. }

复制代码

3. sentinel
使用一个 sentinel 变量来标志一层的结尾。

1. vector<vector<int>> levelOrder(Node *root) {
   
2.     vector<vector<int>> res;
   
3.     vector<int> level;
   
4.     queue<Node*> q;
   
5.     q.push(root);
   
6.     Node *sentinel = new Node(-1);
   
7.     q.push(sentinel);
   
8.     while(!q.empty()) {
   
9.         Node *p = q.front();
   
10.         q.pop();
    
11.         if (p != sentinel) {
    
12.             level.push_back(p->data);
    
13.             if (p->left != nullptr) {
    
14.                 q.push(p->left);
    
15.             }
    
16.             if (p->right != nullptr) {
    
17.                 q.push(p->right);
    
18.             }
    
19.         } else {
    
20.             res.push_back(level);
    
21.             level.clear();
    
22.             if (!q.empty()) q.push(node);
    
23.         }
    
24.     }
    
25. 
    
26.     return res;
    
27. }

复制代码

4. bfs

1. void levelOrder(Node *root) {
   
2.     if (root == nullptr) return;
   
3.     queue<Node*> q;
   
4.     q.push(root);
   
5.     while (!q.empty()) {
   
6.         int n = q.size();
   
7.         while (n--) {
   
8.             Node *p = q.front();
   
9.             q.pop();
   
10.             cout << p->data << " ";
    
11.             if (p->left) q.push(p->left);
    
12.             if (p->right) q.push(p->right);
    
13.         }
    
14.         cout << endl;
    
15.     }
    
16. }

复制代码

5. dfs

1. void levelOrder(Node *root) {
   
2.     function<void(Node*, int, int)> dfs = [&](Node *root, int level, int curLevel) {
   
3.         if (root == nullptr) return;
   
4.         dfs(root->left, level + 1, curLevel);
   
5.         dfs(root->right, level + 1, curLevel);
   
6.     };
   
7. 
   
8.     dfs(root, 0, 0);
   
9. }

复制代码

总结：
思路无非是 BFS 或 DFS，更直观的是 BFS，需要注意的是如何标志一层的结尾，典型的使用到 queue 并且理解 queue 的操作方式。