广度优先搜索 (BFS)

是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法。 该算法从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。

image.png

//我们将树上顶点按照层次依次放入队列结构中，队列中元素满足 FIFO（先进先出）的原则。
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;
    }

深度优先搜索（DFS）
二叉树的遍历： https://www.jianshu.com/p/528bafd9e975
在这个策略中，我们采用深度作为优先级，以便从跟开始一直到达某个确定的叶子，然后再返回根到达另一个分支。

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);
    }

深度优先搜索策略又可以根据根节点、左孩子和右孩子的相对顺序被细分为前序遍历(Preorder)，中序遍历(Inorder)和后序遍历(Postorder)。
下图中的顶点按照访问的顺序编号，按照 1-2-3-4-5 的顺序来比较不同的策略。

image.png