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

思路：

这两题实际是一回事，考察的都是树的层序访问。无非就是在I得到结果后做一次reverse就能得到II要求的结果。无论是树还是图，层序访问最直接的方法就是BFS。

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<vector<int> > levelOrder(TreeNode *root) { vector<vector<int>> levelNodeValues; if(!root) return levelNodeValues; vector<TreeNode*> *curLevel = new vector<TreeNode*>(); vector<TreeNode*> *nextLevel = new vector<TreeNode*>(); curLevel->push_back(root); while(!curLevel->empty()) { // scan curLevel, collect values of curLevel nodes, and generate nextLevel vector<int> curLevelValues; for(int i=0; i<curLevel->size(); 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<TreeNode*> *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<vector<int> > levelOrder(TreeNode *root) { vector<vector<int>> levelNodeValues; if(!root) return levelNodeValues; queue<levelNode> 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<int>(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; } };

注意ln 22-23需要检查当前节点是否在新的一层，如果是新的一层第一个节点，则要相应增加levelNodeValues的尺寸。

3. 层尾标记法

同样用一个queue来进行BFS，但queue的元素仅为TreeNode*而不需要存储节点的层数。在每一层访问完毕时push一个NULL进queue作为一层结束的标记。这种方法的对于平衡binary tree来说增加了log(n)次的push(NULL)和pop()。但如果是非平衡二叉树的极端情况，可能会增加n次的push和pop。

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<vector<int> > levelOrder(TreeNode *root) { vector<vector<int>> levelNodeValues; if(!root) return levelNodeValues; queue<TreeNode*> 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<int>(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的尺寸。

对于Binary Tree Level Order Traversal II，只需要再I的解的基础上，最后再翻转levelNodeValues即可：

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