## [可以识辨每层的BFS]

[细节]

[做法]

pop出root, 像通常BFS一样遍历root的child node，当dequeue分隔符时，在queue里后面插入分隔符

[例题]
Populating Next Right Pointers in Each Node --[From Leetcode]
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
• You may only use constant extra space.
For example,
Given the following binary tree,
1
/  \
2    3
/ \    \
4   5    7
After calling your function, the tree should look like:
1 -> NULL
/  \
2 -> 3 -> NULL
/ \    \
4-> 5 -> 7 -> NULL

[代码]
class Solution {
public:
// BFS Queue
if (root)
bfsq.push_back(root);
bfsq.push_back(dummy);

while (bfsq.size() > 1)
{
if (bfsq[1]!=dummy)
bfsq.front()->next = bfsq[1];
if (bfsq.front()==dummy)
{
bfsq.push_back(dummy);
}
else
{
if (bfsq.front()->left)
bfsq.push_back(bfsq.front()->left);
if (bfsq.front()->right)
bfsq.push_back(bfsq.front()->right);
}
bfsq.erase(bfsq.begin());
}
delete(dummy);
}
};

## [不同方向的BFS]

[细节]

[做法]

pop  S2的时候，把child nodes放入S1里

[例题]
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9  20
/  \
15   7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

[代码]
/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(root==null) return res;
boolean order = true;
ArrayList<TreeNode> toVisit = new ArrayList<TreeNode>();
while(!toVisit.isEmpty()){
ArrayList<TreeNode> next = new ArrayList<TreeNode>();
ArrayList<Integer> temp = new ArrayList<Integer>();
for(TreeNode node:toVisit){
}
for(int i=toVisit.size()-1;i>=0;i--){
TreeNode node = toVisit.get(i);
if(order){
}else{
}
}
order = order?false:true;
toVisit = new ArrayList<TreeNode>(next);
}
return res;
}
}

## [Make use of additional pointers in the Tree for traversal]

[细节]

[例题]
Given a binary tree
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
[代码]
Basic idea is to make use of the next pointer of the current level, iterate through all the nodes on the current level, meanwhile, populate the next pointers of the children below
// the link of level(i) is the queue of level(i+1)
while (n) {
TreeLinkNode * next = NULL; // the first node of next level
TreeLinkNode * prev = NULL; // previous node on the same level
for (; n; n=n->next) {
if (!next) next = n->left?n->left:n->right;

if (n->left) {
if (prev) prev->next = n->left;
prev = n->left;
}
if (n->right) {
if (prev) prev->next = n->right;
prev = n->right;
}
}
n = next; // turn to next level
}
}

## [Bottom up traversal of a tree]

[细节]

２）从叶结点得到很多有用讯息，比如一个特定值是否在当前节点为根的子树存在，或者树的深度等等

[做法]
Recursively visit a tree as you do DFS
However, call the recursive function to left child and right child before you ‘visit’ the root

[例题]
Convert Sorted List to Binary Search Tree

[代码]
Bottom up traversal. The key is call recursion call before you do something about the current node, so that the recursion call chain will finally reach leaf node before you handle the subtree root nodes

public class Solution {

// get list length
int len = 0;
while(ln != null){
len++;
ln = ln.next;
}

return sortedListToBST(0, len - 1);
}

// build bottom-to-top
public TreeNode sortedListToBST(int start, int end) {
// if finished (root)
if(start > end) return null;

// get mid val
int mid = (start + end) / 2;

// build left sub tree
TreeNode left = sortedListToBST(start, mid - 1);
// build root node
root.left = left;
// move to next node to build right sub tree