树的前序、中序、后续、层序遍历（递归与非递归）

一、树的层序遍历（BFS广度优先搜索）

从上到下打印二叉树又称为树的广度优先搜索（BFS）。BFS通常借助队列的先入先出特性来实现。
算法流程：
1、特例处理：当树的根节点为空时，直接返回[];
2、初始化：打印结果列表res = [],包含根节点的队列queue = [root];
3、BFS循环：当队列 queue 为空时跳出；

出队：队首元素出队，记为 node；
打印：将node.val 添加至列表 res 尾部；
添加子节点：若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；
返回值：返回打印结果列表 res 即可。

复杂度分析：

时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次。
空间复杂度 O(N)：最差情况下，即当树为平衡二叉树时，最多有 N/2个树节点同时在 queue 中，使用 O(N) 大小的额外空间。

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[0];
        Queue queue = new LinkedList(){{ add(root); }};
        //等价于queue.add(root);
        ArrayList ans = new ArrayList();
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
       //使用数组存储结果
        int[] res = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++)
            res[i] = ans.get(i);
        return res;
    }
}

二、树的前序、中序、后序、层序遍历（使用递归）

构建二叉树的数据结构

public class BinaryTree {

int val;

BinaryTree left;

BinaryTree right;



public BinaryTree(int val) {

    this.val = val;

}

}

2.1 树的前序遍历

/**
     * 前序遍历
     */
    public void preOrder(BinaryNode<AnyType> Node)
    {
        if (Node != null)
        {
            System.out.print(Node.element + " ");
            preOrder(Node.left);
            preOrder(Node.right);
        }
    }

2.2 树的中序遍历

    /**
     * 中序遍历
     */
    public void midOrder(BinaryNode<AnyType> Node)
    {
        if (Node != null)
        {
            midOrder(Node.left);
            System.out.print(Node.element + " ");
            midOrder(Node.right);
        }
    }

2.3 树的后序遍历

    /**
     * 后序遍历
     */
    public void posOrder(BinaryNode<AnyType> Node)
    {
        if (Node != null)
        {
            posOrder(Node.left);
            posOrder(Node.right);
            System.out.print(Node.element + " ");
        }
    }

2.4 树的层序遍历（BFS广度优先遍历）

    /*
     * 层序遍历
     * 递归
     */
    public void levelOrder(BinaryNode<AnyType> Node) {
        if (Node == null) {
            return;
        }

        int depth = depth(Node);

        for (int i = 1; i <= depth; i++) {
            levelOrder(Node, i);
        }
    }
//======================================================================
    private void levelOrder(BinaryNode<AnyType> Node, int level) {
        if (Node == null || level < 1) {
            return;
        }

        if (level == 1) {
            System.out.print(Node.element + "  ");
            return;
        }

        // 左子树
        levelOrder(Node.left, level - 1);

        // 右子树
        levelOrder(Node.right, level - 1);
    }

//求树的深度==========================================================
public int depth(BinaryNode<AnyType> Node) {
        if (Node == null) {
            return 0;
        }
//递归求树的深度
        int l = depth(Node.left);
        int r = depth(Node.right);
        if (l > r) {
            return l + 1;
        } else {
            return r + 1;
        }
    }
//===================================================================

三、树的前序、中序、后序遍历（不使用递归）

实现Java中非递归实现二叉树的前序、中序、后序、层序遍历，在非递归实现中，借助了栈来帮助实现遍历。前序和中序比较类似，也简单一些，但是后序遍历需要两个栈来进行辅助，稍微复杂一些，层序遍历中借助了一个队列来进行实现。
图片说明

3.1 树的前序遍历

在进行二叉树的前序遍历时，要利用栈，实际上递归实现过程就是程序自己在处理压栈和弹栈。

/**
 * 非递归实现思路：二叉树遍历的递归实现很简单，也很容易理解，
  * 在进行非递归实现时，需要用到栈这种数据结构。
 * 因为递归实现的过程就是程序自己在处理圧栈和弹栈，改用非递归实现时，
  * 用栈模拟系统的圧栈与弹栈，就可以了。
 */

    public List<Integer> preorderBT1(BinaryTree root) {
        List<Integer> preorderResult = new ArrayList<>();
        Stack<BinaryTree> stack = new Stack<>();
        BinaryTree currentNode = root;

        while (currentNode != null || !stack.isEmpty()) {
        //对于前序遍历，需要一直往二叉树的左子树上走，
            //直到左子树走完。在走左子树的过程中需要输出遇到节点的值
            while (currentNode != null) {
                preorderResult.add(currentNode.val);
                stack.push(currentNode);
                currentNode = currentNode.left;
            }

            //左边的节点都走完了，需要改变节点方向
            if (!stack.isEmpty()) {
                currentNode = stack.pop();
                currentNode = currentNode.right;
            }
        }
        return preorderResult;
    }

3.2 树的中序遍历

    /**
     * 中序遍历的非递归实现,与上述前序遍历类似，只有稍许不同，注意
     */
    public List<Integer> inorderBT1(BinaryTree root) {
        List<Integer> inorderResult = new ArrayList<>();
        Stack<BinaryTree> stack = new Stack<>();
        BinaryTree currentNode = root;

        while (currentNode != null || !stack.isEmpty()) {
            //一直向左，但是先不打印经历的节点的值
            while (currentNode != null) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            //到达最左边，打印并改变方向
            if (!stack.isEmpty()) {
                currentNode = stack.pop();
                inorderResult.add(currentNode.val);
                currentNode = currentNode.right;
            }
        }
        return inorderResult;
    }

3.3 树的后序遍历

/** 技巧：妙用前序遍历的非递归可以实现后序遍历的非递归实现， 
这里需要注意几点改变：
后序时，先遍历右，再遍历左，最后将得到的结果反向就好了
*/
public List<Integer> postorderBT1(BinaryTree root) {
    List<Integer> postorderResult = new ArrayList<>();
    Stack<BinaryTree> stack = new Stack<>();
    BinaryTree currentNode = root;

    while (currentNode != null || !stack.isEmpty()) {
        while (currentNode != null) {
            postorderResult.add(currentNode.val);
            stack.push(currentNode);
            currentNode = currentNode.right;
        }
        if (!stack.isEmpty()) {
            currentNode = stack.pop();
            currentNode = currentNode.left;
        }
    }

    Collections.reverse(postorderResult);

    return postorderResult;

}

3.4 树的层序遍历

/**
  * 层次遍历，需要用到队列这种数据结构
 */
    public List<Integer> levelOrderBT(BinaryTree root) {
        List<Integer> levelResult = new ArrayList<>();
        Deque<BinaryTree> deque = new ArrayDeque<>();

        if (root==null)
            return levelResult;
        deque.addLast(root);
        BinaryTree currentNode = root;

        while (!deque.isEmpty()){
            currentNode = deque.pollFirst();
            if (currentNode.left!=null)
                deque.addLast(currentNode.left);
            if (currentNode.right!=null)
                deque.addLast(currentNode.right);
            levelResult.add(currentNode.val);
        }
        return levelResult;

    }

参考链接：
https://www.cnblogs.com/liuyang0/p/6271331.html
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/solution/mian-shi-ti-32-i-cong-shang-dao-xia-da-yin-er-ch-4/
https://blog.csdn.net/qq_30585743/article/details/81274440