按照之字形打印二叉树

清疚 2022-05-24 08:46 204阅读 0赞

![这里写图片描述][70]

import java.util.*;
    
     class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    
    public class Solution {
        //之字形打印二叉树
        public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
              ArrayList<ArrayList<Integer>> re=new ArrayList<ArrayList<Integer>>();
              if(pRoot==null)
                   return re;
              ArrayList<Integer>list=new ArrayList<>();
              LinkedList<TreeNode>queue=new LinkedList<>();
              queue.offer(null);
              queue.offer(pRoot);
              boolean leftToright=true;  //从左向右打印
              while(queue.size()!=1)
              {
                 TreeNode temp=queue.poll();
                 if(temp==null) //为分层分隔符
                 { 
                    Iterator<TreeNode>iterator=null;
                    if(leftToright)
                    {
                         iterator=queue.iterator(); //正向迭代器
                    }else{
                         iterator=queue.descendingIterator(); //反向迭代器
                    }
                    leftToright=!leftToright; //颠倒方向
                    while(iterator.hasNext()){
    
                          TreeNode node=(TreeNode)iterator.next();
                          list.add(node.val);
                    }
                    re.add(new ArrayList<Integer>(list));
                    list.clear();
                    queue.offer(null); //添加分隔符
                    continue;
                 }
                if(temp.left!=null)
                {
                   queue.offer(temp.left);
                }
                if(temp.right!=null)
                {
                   queue.offer(temp.right);
                }
    
              }
    
              return re;
    
        }
    
    
       //二叉树的层序遍历
        public void TreeBFS(TreeNode pRoot)
        {
         Queue<TreeNode> arr=new LinkedList<TreeNode>();//存放元素的队列
         arr.offer(pRoot);
         boolean flag=false;
         while(!arr.isEmpty())
         {
               TreeNode temp=arr.poll();
               System.out.println(temp.val);
                if(temp.left!=null)
                {
                   arr.offer(temp.left);
                }
                if(temp.right!=null)
                {
                   arr.offer(temp.right);
                }
    
         }
    
        }
        public static void main(String[]args){
             //System.out.println("Hello");
            TreeNode root=new TreeNode(1);
            root.left=new TreeNode(2);
            root.right=new TreeNode(3);
            root.left.left=new TreeNode(4);
            root.left.right=new TreeNode(5);
            root.right.left=new TreeNode(6);
            root.right.right=new TreeNode(7);
            Solution s=new Solution();
            s.TreeBFS(root);
            ArrayList<ArrayList<Integer>>arr=s.Print(root);
            for(ArrayList<Integer>arr2:arr)
            {
                 for(int k:arr2)
                 {
                     System.out.print(k+" ");
                 }
                 System.out.println();
            }
    
        }
    
    }

![这里写图片描述][70 1]

[70]: /images/20220524/9d45dff97b234b1c9f38595d50bbb980.png
[70 1]: /images/20220524/cd48b6a7212e475aaf7305a3e04b2400.png