1.分层遍历二叉树：宽度优先遍历

public void levelTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    queue.push(root);
    while (!queue.isEmpty()) {
        TreeNode treeNode = queue.removeFirst();
        System.out.println(treeNode.data);
        if (treeNode.left != null) {
            queue.add(treeNode.left);
        }
        if (treeNode.right != null) {
            queue.add(treeNode.right);
        }
    }
}

2.分层遍历应用，按层打印二叉树

public ArrayList<Integer> printFromTopToBottom(TreeNode root)
{
    ArrayList<Integer> list=new ArrayList<>();
    Queue<TreeNode> queue=new ArrayBlockingQueue<>(100);
    TreeNode last=root;//当前行的最后节点
    TreeNode nLast=root;//下一行的最右节点
    queue.add(root);
    while (!queue.isEmpty())
    {
        TreeNode out=queue.poll();
        System.out.println(out.data+"  ");
        list.add(out.data);
        if (out.left!=null)
        {
            queue.add(out.left);
            nLast=out.left;
        }
        if (out.right!=null)
        {
            queue.add(out.right);
            nLast=out.right;
        }
        if (out==last)
        {
            System.out.println(" ");
            last=nLast;
        }
    }
    return list;
}

3.前序遍历二叉树

public void preorderTraverRec(TreeNode root)
{
    if (root==null)
    {
        return;
    }
    System.out.println(root.data+" ");
    preorderTraverRec(root.left);
    preorderTraverRec(root.right);
}

4.前序遍历，迭代

public void preorderTraversal(TreeNode root)
{
    if (root==null)
    {
        return;
    }
    Stack<TreeNode> stack=new Stack<>();
    stack.push(root);
    while (!stack.isEmpty())
    {
        TreeNode cur=stack.pop();//出栈顶元素
        System.out.println(cur.data+"  ");
        //关键点：要先压入右孩子，再压入左孩子，这样在出栈时会先打印左孩子再打印右孩子
        if (cur.right!=null)
        {
            stack.push(cur.right);
        }
        if (cur.left!=null)
        {
            stack.push(cur.left);
        }
    }
}

5.中顺遍历的迭代算法

public void inorderTraversal(TreeNode root)
{
    if (root==null)
    {
        return;
    }
    Stack<TreeNode> stack=new Stack<>();
    TreeNode cur=root;
    if (cur!=null)
    {
        while (!stack.isEmpty()||cur!=null)
        {
            if (cur!=null)
            {
                stack.push(cur);
                cur=cur.left;
            }
            else
            {
                cur=stack.pop();
                System.out.println(cur.data+"   ");
                cur=cur.right;
            }
        }
    }
}

6.后序遍历

public void postorderTraversal(TreeNode root)
{
    if (root==null)
    {
        return;
    }
    Stack<TreeNode> s=new Stack<TreeNode>();
    Stack<TreeNode> output=new Stack<TreeNode>();
    s.push(root);
    while (!s.isEmpty())
    {
        TreeNode cur=s.pop();
        output.push(cur);
        if (cur.left!=null)
        {
            s.push(cur.left);
        }
        if (cur.right!=null)
        {
            s.push(cur.right);
        }
    }
    while (!output.isEmpty())
    {
        System.out.println(output.pop().data+" ");
    }
}