在层序遍历的基础上修改代码,记录当前层数,对应的层数反转即可。
层序遍历代码:
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return int整型ArrayList<ArrayList<>> */ public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) { // write code here ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>(); if(root==null) return res; Queue<TreeNode> queue=new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ ArrayList<Integer> list=new ArrayList<>(); int count=queue.size(); while(count-->0){ TreeNode node=queue.poll(); list.add(node.val); if(node.left!=null) queue.add(node.left); if(node.right!=null) queue.add(node.right); } res.add(list); } return res; } }
利用层序遍历的结果得到的之字形代码:
import java.util.ArrayList; 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 { public ArrayList<ArrayList<Integer>> Print(TreeNode root) { ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>(); if(root==null) return res; Queue<TreeNode> queue=new LinkedList<>(); queue.add(root); int m=1; while(!queue.isEmpty()){ ArrayList<Integer> list=new ArrayList<>(); int count=queue.size(); while(count-->0){ TreeNode node=queue.poll(); list.add(node.val); if(node.left!=null) queue.add(node.left); if(node.right!=null) queue.add(node.right); } if (m++%2==0) { reverse(list); } res.add(list); } return res; } private static void reverse(ArrayList<Integer> list) { int l=0,r=list.size()-1; while (l<r) { Integer tmp = list.get(l); list.set(l,list.get(r)); list.set(r,tmp); l++; r--; } } }