深度优先遍历和广度优先遍历

深度优先遍历(DFS)

假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：

(1)首先访问出发点v，并将其标记为已访问过；

(2)然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。

(3)若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

>           A
>         /    \
>        B      C
>      /  \    /  
>     E    F  G
>         /
>        I
> 深度遍历结果为： A--B--E--F--I--C--G(假设先走子节点的的左侧)
>

遍历过程如下：

先往栈中压入右节点，再压左节点，这样出栈就是先左节点后右节点了。

(1)首先将A节点压入栈中，stack（A）;

(2)将A节点弹出，同时将A的子节点C，B压入栈中，此时B在栈的顶部，stack(B,C)；

(3)将B节点弹出，同时将B的子节点F，E压入栈中，此时E在栈的顶部，stack（E,F,C）；

(4)将E节点弹出，没有子节点压入,此时E在栈的顶部，stack（F，C）；

(5)将F节点弹出，同时将F的子节点I压入，stack（I,C）；

(6)将I节点弹出，没有子节点压入,此时C在栈的顶部，stack（C）；

(7)将C节点弹出，同时将C的子节点G压入栈中，stack(G)；

(8)将C节点弹出，没有子节点压入，stack为空；

最终遍历完成。

//   class TreeNode {

//        int val;
//        TreeNode left;
//        TreeNode right;
//
//        public TreeNode(int val) {
//            this.val = val;
//        }
//    }
public static ArrayList<Integer> DFS(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            //先往栈中压入右节点，再压左节点，这样出栈就是先左节点后右节点了。
            if(node.right!=null)
                stack.push(node.right);
            if(node.left!=null)
                stack.push(node.left);
            res.add(node.val);
        }
        return res;
    }

递归实现：

class solution{
       ArrayList<Integer> ans = new ArrayList();

       public static ArrayList<Integer> DFS(TreeNode root) {

           if (root != null) {
               ans.add(root.val);
               DFS(root.left);
               DFS(root.right);
           }
           return ans;
       }

}

广度优先遍历(BFS)

广度优先遍历从某个顶点出发，首先访问这个顶点，然后找出这个结点的所有未被访问的邻接点，访问完后再访问这些结点中第一个邻接点的所有结点，重复此方法，直到所有结点都被访问完为止。

1、从图中某个顶点V0出发，并访问此顶点；

2、从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点；

3、重复步骤2，直到全部顶点都被访问为止。

>           A
>         /   \
>        B     C
>      /  \    /
>     E    F  G
>    /
>   I
> 深度遍历结果为： A--B--C--E--F--G--I(假设先走子节点的的左侧)
>

遍历过程如下：

先往队列中插入左节点，再插右节点，这样出队就是先左节点后右节点了。

(1)首先将A节点插入队列中，队列queue（A）;

(2)将A节点弹出，同时将A节点的左、右节点B、C依次插入队列，queue（B，C）；

(3)将B节点弹出，同时将B节点的左、右节点E、F依次插入队列，queue（C, E, F）；

(4将C节点弹出，同时将C节点的左节点G依次插入队列，queue（E , F , G）；

(5)将E节点弹出，同时将E节点的左节点I依次插入队列，queue（F , G , I）；

(6)将F节点弹出，F没有子节点插入，queue（G,I）；

(7)将G节点弹出，G没有子节点插入，queue（I）；

(8)将I节点弹出，I没有子节点插入，queue为空；

最终遍历完成。

实现：

// class TreeNode {
// int val;
// TreeNode left;
// TreeNode right;
//
// public TreeNode(int val) {
// this.val = val;
// }
// }
   public static ArrayList<Integer> BFS(TreeNode root) {
         ArrayList<Integer> res = new ArrayList<>();
         if(root == null)
             return res;
         Queue<TreeNode> queue = new LinkedList<>();
         queue.add(root);
         while (!queue.isEmpty()){
             TreeNode node = queue.poll();
             ////先往queue中压入左节点，再压右节点。
             if(node.left!=null)
                 queue.add(node.left);
             if(node.right!=null)
                 queue.add(node.right);
             res.add(node.val);
         }
         return res;
       }
   }