JAVA实现二叉树的花样层次遍历

上一篇文章记录了二叉树及N叉树的前中后序遍历之后JAVA实现二叉树、N叉树递归/非递归实现前、中、后序遍历，再来记录一下二叉树的花样层次遍历，前中后序遍历非递归主要借助栈这一数据结构，层次遍历主要是借助队列这一数据结构。
这三道题目有点进阶打怪的意思，哈哈~~从最简单的层次遍历开始；再到要求每层输出为一行，就需要知道每层有几个节点了；再到要求之字形打印，那么不只需要知道每层有几个节点，还有要知道当前遍历到那一层了。具体分析如下：

题目解答中用到的TreeNode类，定义如下：

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

从上往下打印二叉树

题目描述：

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

题目解答：

• 由题目描述可以知道这里考察的是二叉树的层次遍历

• 利用队列：先进先出的特性，首先将根节点入队;

• 判断当队不为空的时候，队头元素出队，放入list集合，然后将其左孩子入队，然后将其右孩子入队;

• 注意root为空的情况

  public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<Integer>();
          if (root == null){
              return list;
          }
         Queue<TreeNode> queue = new LinkedList<TreeNode>();
         queue.add(root);
          TreeNode topNode;
          while (!queue.isEmpty()){
              topNode = queue.remove();
              list.add(topNode.val);
              if (topNode.left != null){
                queue.add(topNode.left);
              }
              if (topNode.right != null){
                 queue.add(topNode.right);
              }
          }
          return list;
      }
  

把二叉树打印成多行

题目描述:

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

题目解答：

• 相对于层次遍历的区别在于：每层输出一行；

• 即需要知道每一层的节点个数，将遍历的节点放入list，该行遍历结束之后，将list放入res

• 问题在于如何知道每一层的节点个数？首先知道当前所在层的个数，在遍历当前所在层的时候，计算出下一层的节点个数，当前层遍历结束，更新当前层的节点个数为下一层的节点个数。

  ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
          ArrayList<ArrayList<Integer>> res = new ArrayList<>();
          if (pRoot == null ){
              return res;
          }
          Queue<TreeNode> q = new LinkedList<>();
          q.offer(pRoot);
          //记录每一层的节点个数
          int sum = 1;
          while (!q.isEmpty()){
              ArrayList<Integer> list = new ArrayList<>();
              //当前所在层下一层节点的个数
              int temp = 0;
            while (sum>0){
                TreeNode node = q.remove();
                    list.add(node.val);
                    if (node.left != null){
                        q.offer(node.left);
                        temp++;
                    }
                    if (node.right != null){
                        q.offer(node.right);
                        temp ++;
                    }
                sum --;
            }
            //当前所在层节点操作完成之后，更新sum的值，进行下一层
            sum = temp;
             res.add(list);
          }
          return res;
      }
  

按之字形顺序打印二叉树

题目描述：

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

题目解答：

• 与把二叉树打印成多行相比，区别在于相邻行的打印顺序不同

• 需要知道当前所在行是第几行，若当前行是偶数行需要对list集合进行顺序调整

  public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
          ArrayList<ArrayList<Integer>> res = new ArrayList<>();
  
          if (pRoot == null){
              return res;
          }
          Queue<TreeNode> q = new LinkedList<>();
          q.offer(pRoot);
          //当前所操作的行数
          int row = 1;
          //每层的节点数
          int sum = 1;
          while (!q.isEmpty()){
              ArrayList<Integer> list = new ArrayList<>();
              //当前所在层的下一层节点的个数
              int temp = 0;
              //遍历当前层的所有节点
              while (sum>0){
                  //将队首元素出队
                  TreeNode node = q.remove();
                  list.add(node.val);
  
                  if (node.left != null){
                      q.offer(node.left);
                      temp++;
                  }
  
                  if (node.right != null){
                      q.offer(node.right);
                      temp ++;
                  }
                  sum--;
              }
              sum = temp;
              if (row % 2 ==0){
                  //当前行是偶数行的的话，需要将获得的list数组调整
                  for (int i = 0,j = list.size()-1;i<j;i++,j--){
                      int t = list.get(i);
                      list.set(i,list.get(j));
                      list.set(j,t);
                  }
              }
              row++;
              res.add(list);
          }
          return res;
          
      }
  

转载：https://blog.csdn.net/xl132598798/article/details/105935725