按之字形顺序打印二叉树

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        if(pRoot==null){
            return new ArrayList<>();
        }
        // write code here
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        ArrayList<TreeNode> q=new ArrayList<>();
        int level=1; // 层数
        q.add(pRoot);
        while(q!=null && q.size()>0){
            ArrayList<Integer> subList=new ArrayList<>();
            // 判断是否偶数节点
            if(level%2==0){
                // 如果本层是偶数层，需要将本层倒置后记录本层节点
                Collections.reverse(q);
            }
            // 记录本层节点
            int len=q.size();
            for(int i=0;i<len;i++){
                TreeNode temp=q.get(i);
                subList.add(temp.val);
            }
            list.add(subList); 

            // 录入下一层节点
            if(level%2==0){
                // 如果本层是偶数层，需要将本层恢复正序后录入下一层
                Collections.reverse(q);
            }
            for(int i=0;i<len;i++){
                TreeNode temp=q.get(0);
                if(temp.left!=null){
                    q.add(temp.left);
                }        
                if(temp.right!=null){
                    q.add(temp.right);
                }
                q.remove(0); 
            }
            level+=1;
        }
        return list;
    }
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        // write code here
        // 先正常按照层级收集
        ArrayList<ArrayList<Integer>> r = new ArrayList();
        levelWithRightGetV(pRoot,r,0);
        // 将偶数层级集合进行反转
        for(int i = 0; i < r.size(); i++) {
            if(i % 2 == 1) {
                revList(r.get(i));
            }
        }
        return r;
    }

    public void revList(List<Integer> vs) {
        int size = vs.size() / 2;
        for(int i = 0; i < size; i++) {
            int temp = vs.get(i);
            vs.set(i,vs.get(vs.size() - 1 - i));
            vs.set(vs.size() - 1 - i,temp);
        }
    }

    public void levelWithRightGetV(TreeNode node,ArrayList<ArrayList<Integer>> r,int level) {
        if(node == null) {
            return;
        }
        if(level >= r.size()) {
            r.add(new ArrayList());
        }
        r.get(level).add(node.val);
        levelWithRightGetV(node.left,r,level + 1);
        levelWithRightGetV(node.right,r,level + 1);
    }

    
}

public class Solution {
    /**
     * 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
     *
     *
     * @param pRoot TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (null == pRoot) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> currList = new ArrayList<>();
        queue.offer(pRoot);
        int rootSize = queue.size();//当前层数的总结点数
        while (!queue.isEmpty()) {
            TreeNode top = queue.poll();
            currList.add(top.val);
            if (top.left != null) {
                queue.offer(top.left);
            }
            if (top.right != null) {
                queue.offer(top.right);
            }
            //如果存储的结点数==当前总结点数
            if (currList.size() == rootSize) {
                result.add(currList);
                currList = new ArrayList<>();
                //队列size即为下层节点总数
                rootSize = queue.size();
            }
        }
        //单层反转
        for (int i = 0; i < result.size(); i++) {
            if (i % 2 > 0) {
                Collections.reverse(result.get(i));
            }
        }
        return result;
    }

}

 public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        // 注意这个出入的对称性
        // 从左到右，头出尾入
        // 从右到左，头入尾出 
        // 层序遍历  从左向右  从右向左
        Deque<TreeNode> qu=new LinkedList<>();
        ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
        if(pRoot==null) return ans;
        qu.offer(pRoot);
        while(!qu.isEmpty()){
            //正序
            int level=qu.size();
            ArrayList<Integer> list=new ArrayList<>();
            for(int i=0;i<level;i++){
                TreeNode peek=qu.peekFirst();  //头出   从左到右
                list.add(qu.pollFirst().val);
                if(peek.left!=null) qu.offerLast(peek.left);//尾入
                if(peek.right!=null) qu.offerLast(peek.right);
            }
            ans.add(list);

            if(qu.isEmpty()) break;
            //倒序
            list=new ArrayList<>();
            level=qu.size();
            for(int i=0;i<level;i++){
                TreeNode tmp=qu.peekLast();//尾出   从右到左
                list.add(qu.pollLast().val);
                if(tmp.right!=null) qu.offerFirst(tmp.right);//头入
                if(tmp.left!=null) qu.offerFirst(tmp.left);
            }
            ans.add(list);
        }
        return ans;
    }

import java.util.ArrayList;

import java.util.Map;
import java.util.TreeMap;
import java.util.Optional;

/*
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>> allNodes = new ArrayList<ArrayList<Integer>>();
        Map<Integer, ArrayList<Integer>> levelMap = new
        TreeMap<Integer, ArrayList<Integer>>();
        if (pRoot == null) {
            return allNodes;
        }
        int level = 0;
        ArrayList<Integer> levelNodes = Optional.ofNullable(levelMap.get(level)).orElse(
                                            new ArrayList<Integer>());
        levelNodes.add(pRoot.val);
        levelMap.put(level, levelNodes);
        find(levelMap, pRoot.left, level + 1);
        find(levelMap, pRoot.right, level + 1);
        for (Map.Entry<Integer, ArrayList<Integer>> entry : levelMap.entrySet()) {
            Integer lvl = entry.getKey();
            ArrayList<Integer> list = entry.getValue();
            if (lvl % 2 == 1) {
                allNodes.add(reverse(list));
            } else {
                allNodes.add(list);
            }
        }
        return allNodes;
    }

    public void find(Map<Integer, ArrayList<Integer>> levelMap, TreeNode node,
                     int level) {
        if (node == null) {
            return ;
        }
        ArrayList<Integer> levelNodes = Optional.ofNullable(levelMap.get(level)).orElse(
                                            new ArrayList<Integer>());
        levelNodes.add(node.val);
        levelMap.put(level, levelNodes);
        if (node.left == null && node.right == null) {
            return ;
        } else {
            find(levelMap, node.left, level + 1);
            find(levelMap, node.right, level + 1);
        }
        return;
    }

    public static ArrayList<Integer> reverse(ArrayList<Integer> nodes) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        for (int idx = nodes.size() - 1; idx >= 0; idx--) {
            res.add(nodes.get(idx));
        }
        return res;
    }
}

import java.util.ArrayList;
import java.util.Collections;

/*
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<>();
        depth(pRoot,1,res);
        for (int i = 1; i < res.size(); i+=2) {
                Collections.reverse(res.get(i));
        }
        return res;
    }

    private void depth(TreeNode root,int d,ArrayList<ArrayList<Integer>> list){
        if(root==null) return;
        if(d>list.size()){
            list.add(new ArrayList<Integer>());
        }
        list.get(d-1).add(root.val);
        depth(root.left,d+1,list);
        depth(root.right,d+1,list);
    }
}

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        if (pRoot == null)
            return arrayLists;

        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(pRoot);
        int ceilCount = 0;
        while (!q.isEmpty()) {
            ArrayList<Integer> ceilList = new ArrayList<>();
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                ceilList.add(cur.val);
                if (cur.left != null)
                    q.add(cur.left);
                if (cur.right != null)
                    q.add(cur.right);
            }
            if (ceilCount % 2 != 1) {
                arrayLists.add(ceilList);
            } else {
                Collections.reverse(ceilList);
                arrayLists.add(ceilList);
            }
            ceilCount++;
        }
        return arrayLists;
    }

}

// 层次遍历
import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        if (pRoot == null) return new ArrayList<ArrayList<Integer>>();
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        return depth(queue, true, arrayLists);
    }

    private ArrayList<ArrayList<Integer>> depth(Queue<TreeNode> queue, Boolean left,
            ArrayList<ArrayList<Integer>> arrayLists) {
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> qe = new LinkedList<>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left != null) {
                qe.add(node.left);
            }
            if (node.right != null) {
                qe.add(node.right);
            }
        }
        if (list.size() > 0) {
            if (!left) {
                Collections.reverse(list);
            }
            arrayLists.add(list);
            return depth(qe, !left, arrayLists);
        } else {
            return arrayLists;
        }
    }
}

public class Solution {
    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 deepth = 0;
        while(!q.isEmpty()){
            int sizeLevel = q.size();
            ArrayList<Integer> resLevel = new ArrayList<>();
            while(sizeLevel-->0){
                pRoot = q.poll();
                if(deepth%2==0)resLevel.add(pRoot.val);
                else resLevel.add(0, pRoot.val);
                if(pRoot.left != null) q.offer(pRoot.left);
                if(pRoot.right != null) q.offer(pRoot.right);
            }
            res.add(resLevel);
            deepth++;
        }
        return res;
    }
}