BFS and DFS for traversing a Tree

最近刷关于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实现 - 算法：

1. Create an empty queue q
2. temp_node = root /start from root/
3. 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

Preorder

Postorder