廣度優(yōu)先搜索 (BFS)
是一種廣泛運(yùn)用在樹或圖這類數(shù)據(jù)結(jié)構(gòu)中盟戏，遍歷或搜索的算法咖杂。 該算法從一個(gè)根節(jié)點(diǎn)開始肛循，首先訪問節(jié)點(diǎn)本身。 然后遍歷它的相鄰節(jié)點(diǎn)银择，其次遍歷它的二級鄰節(jié)點(diǎn)多糠、三級鄰節(jié)點(diǎn)，以此類推浩考。
image.png
//我們將樹上頂點(diǎn)按照層次依次放入隊(duì)列結(jié)構(gòu)中夹孔，隊(duì)列中元素滿足 FIFO（先進(jìn)先出）的原則。
public IList<IList<int>> LevelOrder(TreeNode root) {
if (root == null)
return new List<IList<int>>();
List<IList<int>> res = new List<IList<int>>();
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count!=0)
{
int count = queue.Count;
List<int> list = new List<int>();
while (count > 0)
{
TreeNode node = queue.Dequeue();
list.Add(node.val);
if (node.left != null)
queue.Enqueue(node.left);
if (node.right != null)
queue.Enqueue(node.right);
count--;
}
res.Add(list);
}
return res;
}
深度優(yōu)先搜索（DFS）
二叉樹的遍歷： http://www.reibang.com/p/528bafd9e975
在這個(gè)策略中析孽，我們采用深度作為優(yōu)先級搭伤，以便從跟開始一直到達(dá)某個(gè)確定的葉子，然后再返回根到達(dá)另一個(gè)分支袜瞬。
public IList<IList<int>> LevelOrder(TreeNode root) {
List<IList<int>> list = new List<IList<int>>();
Level(root,0,list);
return list;
}
public void Level(TreeNode node ,int level,List<IList<int>> list){
if(node==null)
return;
if(level>=list.Count)
list.Add(new List<int>());
list[level].Add(node.val);
Level(node.left,level+1,list);
Level(node.right,level+1,list);
}
深度優(yōu)先搜索策略又可以根據(jù)根節(jié)點(diǎn)怜俐、左孩子和右孩子的相對順序被細(xì)分為前序遍歷(Preorder)，中序遍歷(Inorder)和后序遍歷(Postorder)邓尤。
下圖中的頂點(diǎn)按照訪問的順序編號拍鲤，按照 1-2-3-4-5 的順序來比較不同的策略。
image.png
