本文共 2017 字，大约阅读时间需要 6 分钟。

题目描述

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

第一种思路：也是从左到右来进行遍历，只不过是在该反转的时候用collections工具类进行反转，代码如下：

public ArrayList
   
    
     > Print(TreeNode pRoot) {    ArrayList
     
      
       > ret = new ArrayList<>();    Queue
       
         queue = new LinkedList<>();    queue.add(pRoot);    boolean reverse = false;    while (!queue.isEmpty()) {        ArrayList
        
          list = new ArrayList<>(); int cnt = queue.size(); while (cnt-- > 0) { TreeNode node = queue.poll(); if (node == null) continue; list.add(node.val); queue.add(node.left); queue.add(node.right); } if (reverse) Collections.reverse(list); reverse = !reverse; if (list.size() != 0) ret.add(list); } return ret;}
        
       
      
     
    
   

第二种方法是用到stack栈：

package cn.cqu.edu;import java.util.ArrayList;import java.util.Stack;public class Print {		class TreeNode {	    int val = 0;	    TreeNode left = null;	    TreeNode right = null;	    public TreeNode(int val) {	        this.val = val;	    }	}	    public ArrayList
   
    
     > Print(TreeNode pRoot) {    	    	ArrayList
     
       ele=new ArrayList
      
       ();    	ArrayList
       
        
         > list=new ArrayList
         
          
           >(); if(pRoot==null) { return list; } int i=0; //奇数表示从左到右，偶数表示从右到左,注意这里描述的是进栈的顺序 Stack
           
             previousStack1=new Stack<>(); previousStack1.push(pRoot); while(!previousStack1.isEmpty()) { Stack
            
              currentStack2=new Stack<>(); i++; ArrayList
             
               e=new ArrayList
              
               (); int n=previousStack1.size(); if(i%2==0) //从右到左 { while(!previousStack1.isEmpty()) { TreeNode node=previousStack1.pop(); e.add(node.val); if(node.right!=null) { currentStack2.add(node.right); } if(node.left!=null) { currentStack2.add(node.left); } } } else { while(!previousStack1.isEmpty()) { TreeNode node=previousStack1.pop(); e.add(node.val); if(node.left!=null) { currentStack2.add(node.left); } if(node.right!=null) { currentStack2.add(node.right); } } } list.add(e); previousStack1=currentStack2; } return list; } public static void main(String[] args) { }}
              
             
            
           
          
         
        
       
      
     
    
   

第二种方法不如第一种好

转载地址：http://hdkmi.baihongyu.com/