那些年我们一起遍历过的树

这篇博文想和大家讨论一下tree的traversal有哪些方法。当然我们都很熟悉DFS(InOrder, PreOrder, PostOrder)和BFS，这篇我们想谈一下一些其他方法以及DFS BFS的变种

[可以识辨每层的BFS]

[细节]

在题目中，我们时常需要做BFS并且要区分树的层与层，然后利用这个信息完成任务

[做法]

使用一个queue

初始化queue里插入root和一个分割符（普通node是pointer,因此分割符可选用特殊数字）

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

......