最近刷关于Tree的题遇到了不少用BFS/DFS解决的问题，鉴于自己对概念一知半解，翻出之前一个朋友推荐过的文章学习一下。
原文地址：https://www.geeksforgeeks.org/level-order-tree-traversal/
BFS vs DFS for Binary Tree
What are BFS and DFS for Binary Tree?
A Tree is typically traversed in two ways:
- Breadth First Traversal (Or Level Order Traversal)
-
Depth First Traversals
- Inorder Traversal (Left-Root-Right)
- Preorder Traversal (Root-Left-Right)
-
Postorder Traversal (Left-Right-Root)
Example Tree
Depth First Traversals:
(a) Inorder (Left, Root, Right) : 4 2 5 1 3
(b) Preorder (Root, Left, Right) : 1 2 4 5 3
(c) Postorder (Left, Right, Root) : 4 5 2 3 1
注意：in, pre, post 是实现DFS的三种方式。
Breadth First or Level Order Traversal : 1 2 3 4 5
Please see this post for Breadth First Traversal.
printLevelorder(tree)
通常有两种实现方式：
Iteration
Queue
BFS - Queue实现 - 算法：
- Create an empty queue q
- temp_node = root /start from root/
- Loop while temp_node is not NULL
a) print temp_node->data.
b) Enqueue temp_node’s children (first left then right children) to q
c) Dequeue a node from q and assign it’s value to temp_node
DFS的三种实现方式
Inorder
对于BST，使用Inorder方式输出可以使得结点升序排列。
PS. Sorted Array to BST - 参见LC.107
