二叉树的深度优先遍历和广度优先遍历

概述：


1、深度优先遍历（Depth-First-Search）常用的数据结构为栈，广度优先遍历（Breadth-First-Search）常用的数据结构为队列

2、深度优先遍历的思想是从上至下，对每一个分支一直往下一层遍历直到这个分支结束，然后返回上一层，对上一层的右子树这个分支继续深搜，直到一整棵树完全遍历，因此深搜的步骤符合栈后进先出的特点

广度优先遍历的思想是从左至右，对树的每一层所有结点依次遍历，当一层的结点遍历完全后，对下一层开始遍历，而下一层结点又恰好是上一层的子结点。因此广搜的步骤符合队列先进先出的思想

3、深度优先遍历：

对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。
要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为前序遍历、中序遍历、后序遍历。

前序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树，前序就是根节点在最前：根->左->右。

中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树，中序是根节点在中间：左->根->右。

后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根，后序是根节点在最后：左->右->根。

除了利用栈以外，深度优先搜索也可以使用递归的方法。

4、广度优先遍历：

又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。


5、深度优先搜索算法：不全部保留结点，占用空间少；有回溯操作(即有入栈、出栈操作)，运行速度慢。

通常深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，一般在数据库中存储的结点数就是深度值，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。

广度优先搜索算法：保留全部结点，占用空间大； 无回溯操作(即无入栈、出栈操作)，运行速度快。

广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。



代码：

public class TreeTravel {

/**
* 前序遍历：递归法
*
* 递归的方法很容易实现，也很容易理解：我们先访问根节点，然后递归访问左子树，再递归访问右子树，即实现了根->左->右的访问顺序，
* 因为使用的是递归方法，所以每一个子树都实现了这样的顺序。
* @param root
* @return
*/
public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        preorderHelper(root, result);
        return result;
    }

    private void preorderHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        result.add(root.val); // 访问根节点
        preorderHelper(root.left, result); // 递归遍历左子树
        preorderHelper(root.right, result); //递归遍历右子树
    }
   
    /**
     * 前序遍历：迭代法
     *
     * 在迭代法中，我们使用栈来实现。由于出栈顺序和入栈顺序相反，所以每次添加节点的时候先添加右节点，再添加左节点。
     * 这样在下一轮访问子树的时候，就会先访问左子树，再访问右子树：
     */
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if (root == null) return result;

        Stack<TreeNode> toVisit = new Stack<>();
        toVisit.push(root);
        TreeNode cur;

        while (!toVisit.isEmpty()) {
            cur = toVisit.pop();
            result.add(cur.val); // 访问根节点
            if (cur.right != null) toVisit.push(cur.right); // 右节点入栈
            if (cur.left != null) toVisit.push(cur.left); // 左节点入栈
        }
        return result;
    }
   
    /**
     * 中序遍历：递归法
     *
     * 对于中序遍历，就是先访问左子树，再访问根节点，再访问右子树，即 左->根->右
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        inorderHelper(root, result);
        return result;
    }
   
    private void inorderHelper(TreeNode root, List<Integer> result) {
        if(root == null) return;
        inorderHelper(root.left, result); // 递归遍历左子树
        result.add(root.val); // 访问根节点
        inorderHelper(root.right, result); // 递归遍历右子树
    }
   
    /**
     * 中序遍历：迭代法
     *
     * 因为最先遇到的根节点不是最先访问的，我们需要先访问左子树，再回退到根节点，再访问根节点的右子树，
     * 这里的一个难点是从左子树回退到根节点的操作，虽然可以用栈来实现回退，但是要注意在出栈时保存根节点的引用，
     * 因为我们还需要通过根节点来访问右子树
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> toVisit = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !toVisit.isEmpty()) {
            while (cur != null) {
                toVisit.push(cur); // 添加根节点
                cur = cur.left; // 循环添加左节点
            }
            cur = toVisit.pop(); // 当前栈顶已经是最底层的左节点了，取出栈顶元素，访问该节点
            result.add(cur.val);
            cur = cur.right; // 添加右节点
        }
        return result;
    }
   

    /**
     * 后序遍历：递归法
     *
     * 对于后序遍历，就是先访问左子树，再访问右子树，再访问根节点，即 左->右->根
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        postorderHelper(root, result);
        return result;
    }

    private void postorderHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        postorderHelper(root.left, result); // 遍历左子树
        postorderHelper(root.right, result); // 遍历右子树
        result.add(root.val); // 访问根节点
    }
   
    /**
     * 后序遍历：迭代法
     *
     * 后序遍历在访问完左子树向上回退到根节点的时候不是立马访问根节点的，
     * 而是得先去访问右子树，访问完右子树后在回退到根节点
     */
    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> toVisit = new Stack<>();
        TreeNode cur = root;
        TreeNode pre = null;

        while (cur != null || !toVisit.isEmpty()) {
            while (cur != null) {
                toVisit.push(cur); // 添加根节点
                cur = cur.left; // 递归添加左节点
            }
            cur = toVisit.peek(); // 已经访问到最左的节点了
            //在不存在右节点或者右节点已经访问过的情况下，访问根节点
            if (cur.right == null || cur.right == pre) {
                toVisit.pop();
                result.add(cur.val);
                pre = cur;
                cur = null;
            } else {
                cur = cur.right; // 右节点还没有访问过就先访问右节点
            }
        }
        return result;
    }
   
   
    /**
     * 广度优先遍历
     *
     * 广度优先遍历各个节点，需要使用到队列（Queue）这种数据结构，queue的特点是先进先出
     */   
    public ArrayList<Integer> wide(TreeNode root) {
        ArrayList<Integer> lists=new ArrayList<Integer>();
        if(root==null)
            return lists;
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
            lists.add(node.val);
          }
        return lists;
    }
   
   
}