思路:和广度优先搜索一样的思路,只是每隔一层需要将元素倒置,这里只需使用ArrayList的头插法即可。
public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) { if(root==null ) return new ArrayList<>(); ArrayList<ArrayList<Integer>> result=new ArrayList<>(); //返回result,存储每层节点 Queue<TreeNode> queue=new LinkedList<>(); queue.add(root); //放入根节点 int level=1; //定义层数,根节点为第一层 while(!queue.isEmpty()){ ArrayList<Integer> arr=new ArrayList<>(); //放置每一层节点的动态数组,每次循环将被重置 //计数每层的节点,进行循环放入ArrayList数组中 int levelNum=queue.size(); for(int i=0;i<levelNum;i++){ TreeNode node=queue.poll(); //判断是奇数层还是偶数层,偶数层需要使用头插法 if(level%2!=0){ arr.add(node.val); }else{ arr.add(0,node.val); } //加入节点的左右子树 if(node.left!=null) queue.add(node.left); if(node.right!=null) queue.add(node.right); } result.add(arr); level++; //一层增加一 } return result; } }