这篇博文想和大家讨论一下tree的traversal有哪些方法。当然我们都很熟悉DFS(InOrder, PreOrder, PostOrder)和BFS,这篇我们想谈一下一些其他方法以及DFS 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:
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
......