JZ59：按之字形顺序打印二叉树

使用链表的辅助空间来实现，利用链表的反向迭实现逆序输出

解法1：增加两个TreeNode：last和nlast
last：表示当前遍历层最右结点
nlast：表示下一层最右结点
遍历时，每次将nlast指向插入队列元素，最后一个插入结点时即最右结点。插入左右孩子之后，检测last是否为当前输出结点，若是，则表示需要进行换行，并将last指向下一层的nlast。

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
/*
public 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>> list=new ArrayList<ArrayList<Integer>>();
        if(pRoot==null){
            return list;
        }
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(pRoot);
        TreeNode last=pRoot;
        TreeNode nlast=pRoot;
        boolean flag=true;
        ArrayList<Integer> res=new ArrayList<Integer>();
        while(!queue.isEmpty()){
            TreeNode tmp=queue.poll();
            res.add(tmp.val);

            if(tmp.left!=null){
                queue.add(tmp.left);
                nlast=tmp.left;
            }
            if(tmp.right!=null){
                queue.add(tmp.right);
                nlast=tmp.right;
            }
            if(tmp==last){
                list.add(reverse(res,flag));
                flag=!flag;
                last=nlast;
                res=new ArrayList<Integer>();
            }
        }
        return list;
    }
    public ArrayList<Integer> reverse(ArrayList<Integer> list,boolean flag){
        if(flag==false){
            ArrayList<Integer> res=new ArrayList<Integer>();
            for(int i=list.size()-1;i>=0;i--){
                res.add(list.get(i));
            }
            return res;
        }
        else{
            return list;
        }
    }
} 

解法2：

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(pRoot == null)
            return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(pRoot);
        int dep = 0;
        while(!q.isEmpty()){
            LinkedList<Integer> list = new LinkedList<>();
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeNode node = q.poll();
                if(dep%2 == 0){
                    list.add(node.val);
                }else{
                    list.addFirst(node.val);
                }
                if(node.left != null)
                    q.add(node.left);
                if(node.right != null)
                    q.add(node.right);
            }
            dep++;
            res.add(new ArrayList(list));
        }
        return res;
    }

代码2：

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
/*
public 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>> res=new ArrayList<ArrayList<Integer>>();
        if(pRoot==null){
            return res;
        }
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(pRoot);
        int depth=0;
        while(!queue.isEmpty()){
            int size=queue.size();
            ArrayList<Integer> list=new ArrayList<Integer>();
            for(int i=0;i<size;i++){
                TreeNode tmp=queue.poll();
                list.add(tmp.val);
                if(tmp.left!=null){
                    queue.add(tmp.left);
                }
                if(tmp.right!=null){
                    queue.add(tmp.right);
                }
            }
            depth++;
            if(depth%2==1){
                res.add(list);
            }
            else{
                res.add(reverse(list));
            }
        }
        return res;
    }
    public ArrayList<Integer> reverse(ArrayList<Integer> list){
        ArrayList<Integer> res=new ArrayList<Integer>();
        for(int i=list.size()-1;i>=0;i--){
            res.add(list.get(i));
        }
        return res;
    }
}

利用两个栈的辅助空间分别存储奇数偶数层的节点，然后打印输出。

import java.util.Stack;
public ArrayList<ArrayList<Integer>> ZiZapPrint(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();

        if(pRoot==null){
            return res;
        }

        Stack<TreeNode> stack1=new Stack<TreeNode>();
        Stack<TreeNode> stack2=new Stack<TreeNode>();

        stack1.push(pRoot);
        int level=1;
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            if(level%2==1){
                ArrayList<Integer> list=new ArrayList<Integer>();
                while(!stack1.isEmpty()){
                    TreeNode node=stack1.pop();
                    if(node!=null){
                        list.add(node.value);//把结点值加到list
                        stack2.push(node.left);//因为偶数层，先右后左，所以栈里先放左子树
                        stack2.push(node.right);
                    }
                }
                if(!list.isEmpty()){
                    res.add(list);
                    level++;
                }
            }
            else{
                ArrayList<Integer> list=new ArrayList<Integer>();
                while(!stack2.isEmpty()){
                    TreeNode node=stack2.pop();
                    if(node!=null){
                        list.add(node.value);//把结点值加到list
                        stack1.push(node.right);//因为奇数层，先左后右，所以栈里先放右子树
                        stack1.push(node.left);
                    }
                }
                if(!list.isEmpty()){
                    res.add(list);//偶数层的结点加到res
                    level++;
                }
            }
        }
        return res;
    }