Q：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
A：BFS，偶数层reverse
vector<vector<int> > Print(TreeNode *pRoot) {
vector<vector<int> > result;
if (pRoot == nullptr)
return result;
bool rever = false;
TreeNode *temp;
queue<TreeNode *> queue;
queue.push(pRoot);
int count = 1;
vector<int> temp0;
while (!queue.empty()) {
while (count-- != 0) {
temp = queue.front();
temp0.push_back(temp->val);
queue.pop();
if (temp->left)
queue.push(temp->left);
if (temp->right)
queue.push(temp->right);
}
count = queue.size();
if (!rever) {
rever = true;
} else {
reverse(temp0.begin(), temp0.end());
rever = false;
}
result.push_back(temp0);
temp0.clear();
}
return result;
}
Q：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
A：BFS，比上面还简单，不用reverse（摊手）
vector<vector<int> > Print(TreeNode *pRoot) {
vector<vector<int> > result;
if (pRoot == nullptr)
return result;
bool rever = false;
TreeNode *temp;
queue<TreeNode *> queue;
queue.push(pRoot);
int count = 1;
vector<int> temp0;
while (!queue.empty()) {
while (count-- != 0) {
temp = queue.front();
temp0.push_back(temp->val);
queue.pop();
if (temp->left)
queue.push(temp->left);
if (temp->right)
queue.push(temp->right);
}
count = queue.size();
result.push_back(temp0);
temp0.clear();
}
return result;
}
Q：给定一个二叉树，返回该二叉树由底层到顶层的层序遍历，（从左向右，从叶子节点到根节点，一层一层的遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
3↵ / ↵ 9 20↵ / ↵ 15 7
该二叉树由底层到顶层层序遍历的结果是
[↵ [15,7]↵ [9,20],↵ [3],↵]
如果你不清楚“{1,#,2,3}"的含义的话，请继续阅读
OJ用这样的方法将二叉树序列化：
二叉树的序列化遵循层序遍历的原则，”#“代表该位置是一条路径的终结，下面不再存在结点。
例如：
1↵ / ↵ 2 3↵ /↵ 4↵ ↵ 5
上述的二叉树序列化的结果是："{1,2,3,#,#,4,#,#,5}".
A：层序遍历，每次添加到0的位置上
public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
ArrayList<ArrayList<Integer>> wrapList = new ArrayList<ArrayList<Integer>>();
if(root == null) return wrapList;
queue.offer(root);
while(!queue.isEmpty()){
int levelNum = queue.size();
ArrayList<Integer> subList = new ArrayList<Integer>();
for(int i=0; i<levelNum; i++) {
if(queue.peek().left != null) queue.offer(queue.peek().left);
if(queue.peek().right != null) queue.offer(queue.peek().right);
subList.add(queue.poll().val);
}
//每次将结果保存到下标为0的位置
wrapList.add(0, subList);
}
return wrapList;
}