## Tuesday, November 11, 2014

### [LeetCode] Binary Tree Level Order Traversal I, II

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

Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree `{3,9,20,#,#,15,7}`,
```    3
/ \
9  20
/  \
15   7
```
return its bottom-up level order traversal as:
```[
[15,7],
[9,20],
[3]
]
```

1. BFS可以用一个queue实现，但是难以跟踪每个节点究竟是在第几层。解决办法是除了压入节点指针外，还同时压入节点所在的层数，即压入pair<TreeNode*, int>。

2. 层序访问更直接的方法是将当前层的节点和下一层的节点分别保存在两个container curLevel和nextLevel中（vector, queue, stack都可以，取决于具体要求）。每次扫描curLevel中的节点，并将其左右子节点更新到nextLevel中。当curLevel所有节点扫描过后，该层已经遍历完整，swap curLevel和nextLevel即可继续访问。

1. 两个container的迭代解法

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30``` ```class Solution { public: vector > levelOrder(TreeNode *root) { vector> levelNodeValues; if(!root) return levelNodeValues; vector *curLevel = new vector(); vector *nextLevel = new vector(); curLevel->push_back(root); while(!curLevel->empty()) { // scan curLevel, collect values of curLevel nodes, and generate nextLevel vector curLevelValues; for(int i=0; isize(); i++) { TreeNode *curNode = (*curLevel)[i]; curLevelValues.push_back(curNode->val); if(curNode->left) nextLevel->push_back(curNode->left); if(curNode->right) nextLevel->push_back(curNode->right); } levelNodeValues.push_back(curLevelValues); //swap curLevel and nextLevel, and clear nextLevel vector *temp = curLevel; curLevel = nextLevel; nextLevel = temp; nextLevel->clear(); } return levelNodeValues; } }; ```

2. 单个queue的迭代解法

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32``` ```class Solution { struct levelNode { TreeNode *node; int level; levelNode(TreeNode *nd, int lvl):node(nd), level(lvl){} }; public: vector > levelOrder(TreeNode *root) { vector> levelNodeValues; if(!root) return levelNodeValues; queue q; q.push(levelNode(root,0)); while(!q.empty()) { levelNode curLevelNode = q.front(); TreeNode *curNode = curLevelNode.node; int curLevel = curLevelNode.level; q.pop(); if(curLevel==levelNodeValues.size()) levelNodeValues.push_back(vector(0,0)); levelNodeValues[curLevel].push_back(curNode->val); if(curNode->left) q.push(levelNode(curNode->left,curLevel+1)); if(curNode->right) q.push(levelNode(curNode->right,curLevel+1)); } return levelNodeValues; } }; ```

3. 层尾标记法

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

ln 9：在压入root后，需要额外压入一个NULL来标记第0层尾。
ln 18：只有在q不为空时才压入层尾标记NULL。少了这个判断，则在处理最后一个NULL时会陷入死循环——不断取出一个NULL，再压回一个NULL。
ln 22-23：和方法2中一样，对新的一层要扩展levelNodeValues的尺寸。

 `1` ```reverse(levelNodeValues.begin(),levelNodeValues.end()); ```