二叉树的层次遍历及之形打印算法 Java实现

最近在面试和学习中发现对于二叉树的层次遍历算法，java语言的实现尚不明确，在查阅资料，总结前人经验的基础上，把算法代码实现记录在此，加深学习理解，方便日后查看。

基于java实现二叉树层次遍历的思想，要借助数据结构队列的先进先出的功能，先将根节点入队，在队不为空的条件下while循环，当前节点是队头节点，将其出队并访问，如果当前节点的左节点不为空将左节点入队，如果当前节点的右节点不为空将其入队。这样保证了出队顺序也是从左到右依次出队。

代码实现如下：

import java.util.LinkedList;  

public class LevelOrder {  
  public void levelIterator(BiTree root)  
  {  
      if(root == null)  
      {  
          return ;  
      }  
      LinkedList<BiTree> queue = new LinkedList<BiTree>();  
      BiTree current = null;  
      queue.offer(root);//将根节点入队 
      while(!queue.isEmpty())  
      {  
          current = queue.poll();//出队队头元素并访问 
          System.out.print(current.val +"-->");  
          if(current.left != null)//如果当前节点的左节点不为空入队 
          {  
              queue.offer(current.left);  
          }  
          if(current.right != null)//如果当前节点的右节点不为空，把右节点入队 
          {  
              queue.offer(current.right);  
          }  
      }         
  }     
}  

在二叉树层次遍历的基础上，面试过程中经常会碰到扩展的算法题，按之字形打印二叉树节点，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

解题思路

1. 使用两个辅助栈来分别存储奇数层节点和偶数层节点。
2. 注意两个栈的插入顺序是不同的。
3. 对于奇数层来说，也就是从左往右的顺序，先添加左子树，然后添加右子树。对于偶数层，刚好相反，先添加右子树，然后添加左子树。

代码实现如下：

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        int level = 1;
        //s1存奇数层节点
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        s1.push(pRoot);
        //s2存偶数层节点
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        while (!s1.empty() || !s2.empty()) {
            if (level%2 != 0) {
                ArrayList<Integer> temp = new ArrayList<Integer>();
                while (!s1.empty()) {
                    TreeNode node = s1.pop();
                    if(node != null) {
                        temp.add(node.val);
                        s2.push(node.left);
                        s2.push(node.right);
                    }
                }
                if (!temp.isEmpty()) {
                    list.add(temp);
                    level++;
                    }
            } else {
                    ArrayList<Integer> temp = new ArrayList<Integer>();
                    while (!s2.empty()) {
                        TreeNode node = s2.pop();
                        if(node != null) {
                            temp.add(node.val);
                            s1.push(node.right);
                            s1.push(node.left);
                        }
                    }
                    if (!temp.isEmpty()) {
                        list.add(temp);
                        level++;
                    }
                }
            }
        return list;
    }
}