最近刷關(guān)于Tree的題遇到了不少用BFS/DFS解決的問題驴一，鑒于自己對(duì)概念一知半解特石，翻出之前一個(gè)朋友推薦過(guò)的文章學(xué)習(xí)一下挖函。
原文地址：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 是實(shí)現(xiàn)DFS的三種方式论咏。
Breadth First or Level Order Traversal : 1 2 3 4 5
Please see this post for Breadth First Traversal.
printLevelorder(tree)
通常有兩種實(shí)現(xiàn)方式：
Iteration
Queue
BFS - Queue實(shí)現(xiàn) - 算法：
- 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的三種實(shí)現(xiàn)方式
Inorder
對(duì)于BST，使用Inorder方式輸出可以使得結(jié)點(diǎn)升序排列袍嬉。
PS. Sorted Array to BST - 參見LC.107
