实现树的深度优先搜索(DFS)和广度优先搜索(BFS)

1.深度优先遍历(DFS)

深度优先搜索 (depth first search，DFS)是对先序遍历的推广，我们从某个顶点A开始处理A，然后递归遍历所有与A节点邻接的顶点。当访问一个顶点A的时候，由于我们当时已经到了该点处，因此可以标记该点是访问过的，并且对于尚未被标记的所有邻接顶点递归调用DFS进行计算。

简单说：DFS就是先尽可能达到当前遍历路径能够达到最长的路径，一旦达到该路径终点，再回溯，从原来已遍历过顶点处开始新的分支路径的遍历。
深度优先遍历各个节点，需要使用到栈（Stack）这种数据结构。Stack的特点是是先进后出，首先将右节点压入栈中，在将左节点压入栈中，这样出栈顺序就是先左节点再右节点。

整个遍历过程如下：首先将A节点压入栈中，stack（A）;

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

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

将D节点弹出，由于D没有子节点压入，此时E在栈的顶部，stack（E，C）；

将E节点弹出，同时将E的子节点H压入，stack（H,C）；

将H节点弹出，由于H没有子节点压入，此时C在栈的顶部，同时将C的G，F子节点压入栈中，stack（C，F，G）；

…依次往下，最终遍历完成，遍历结果是：A，B，D，E，H，C，F，I，G。

（1）非递归代码实现如下：

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
 
public class Main1 {
    public ArrayList<Integer> DfsTree(TreeNode root) {
        ArrayList<Integer> lists = new ArrayList<I>();
        if(root == null)
            return lists;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode tree = stack.pop();
　　　　　　//先往栈中压入右节点，再压左节点，出栈就是先左节点后出右节点了(先序遍历推广)。
            if(tree.right != null)
                stack.push(tree.right);
            if(tree.left != null)
                stack.push(tree.left);
            lists.add(tree.val);
        }
        return lists;
    }
}

（2）递归代码实现DFS如下：

 
      
private void DfsRecursive(TreeNode root){ 
 
     if (root != null)   
    {  
       System.out.print(root.value+"  ");  
       DfsRecursive(root.left);  
       DfsRecursive(root.right);  
    }         
}

2.广度优先遍历(BFS)

广度优先搜索基本操作是和深度优先差不多的，只不过这里是通过队列来实现的，找到一个起点A，并将A相邻的点放入队列中，这时将队首元素B取出，并将B相邻且没有访问过的点放入队列中，不断重复这个操作，直至队列清空，这个时候依次访问的顶点就是遍历的顺序。
广度优先遍历树，需要用到队列（Queue）来存储节点对象，队列的特点就是先进先出。先往队列中插入左节点，再插入右节点，队列出队就是先出左节点，再出右节点。

首先将A节点插入队列中，队列中有元素（A）;

将A节点弹出，同时将A节点的左节点B、右节点C依次插入队列，B在队首，C在队尾，（B，C），此时得到A节点；

将队首元素B弹出，并将B的左节点D、右节点E插入队列，C在队首，E在队尾（C，D，E），此时得到B节点；

再将队首元素C弹出，并将C节点的左节点F，右节点G依次插入队列，（D，E，F，G），此时得到C节点；

将D弹出，此时D没有子节点，队列中元素为（E，F，G），得到D节点；

。。。以此类推。最终的遍历结果为：A，B，C，D，E，F，G，H，I。

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
 
    public TreeNode(int val) {
        this.val = val;
 
    }
 
}
*/
 
public class Main2{
    public ArrayList<Integer> BfsTree(TreeNode root) {
        ArrayList<Integer> lists = new ArrayList<>();
        if(root == null)
            return lists;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode tree = queue.poll();
            if(tree.left != null)
                queue.offer(tree.left);
            if(tree.right != null)
                queue.offer(tree.right);
            lists.add(tree.val);
        }
        return lists;
    }
}