LeetCode 中Tree的BFS

Tree 的BFS往往指的是层序遍历已经层序遍历的变型。最常见的做法是用两个queue，交替表示当前层和下一层。这种做法思路清晰简单，但是空间耗费是O（n）。 有些时候会要求更巧妙的空间耗费少的办法。
1. Binary Tree Level Order Traversal
也可以用递归的方法来做：
2. Binary Tree ZigZag Level Order Traversal
因为是zigzag顺序，因此用stack而不是queue，反序时先放left后放right，正序时先放right后放left。
3. Binary Tree Level Order Traversal II
题目由自顶向下改为了自底向上，只要把题1的结果reverse即可。这里代码略去
4. Populating Next Right Pointers in Each Node
此题是按层遍历的变种，用到双层 queue。注意此题的假设树是完全二叉树(perfect binary tree)
还有一种O（1）空间的解法，两个节点node负责换层(node=node->left), cross负责把左右子树连起来，以及右子树和corss->next的左子树连起来。
5. Populating Next Right Pointers in Each Node II
此题输入是任意的二叉树，因此并不是左右子树都存在，要分别考虑。代码很简单只需要改动两行
空间O（1）的解法，需要先把下一层链接好然后 用next来遍历下一层。 在开始遍历每一层前，next和pre都为0，这是位了发现正确的next（下层第一个非空孩子）和pre（下层第一个非空孩子）