树的层序遍历可以使用队列实现,队列的思想是一头进,一头出,而如果ArrayList同样能实现队列,但是ArrayList增删需要移动大量元素,会比较耗时,因此使用linkedlist会更加高效。
主要问题:题目要求返回的是一个ArrayList<ArrayList<integer>>对象,也就是一层的节点数据存在一个ArrayList<integer>中,因此需要记录每一层的节点个数,并将这些节点保存在一个ArrayList<integer>中
主要思路:</integer></integer></integer>
- 设置变量: int count=1;int pre=count;
- 每从队头获取一个元素,pre--;count--;
- 每添加一个节点到队列中,count++,每(访问)删除一个节点count--
- 如果pre==0设置pre=count,
设置pre的目的也就是确定一层节点的边界
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>> retArray=new ArrayList<ArrayList<Integer>>(); LinkedList<TreeNode> list=new LinkedList<>(); if(root!=null) list.add(root); int count=1; int pre=count; ArrayList<Integer> levelArray=new ArrayList<Integer>(); while(list.size()>0){ TreeNode temp=list.remove(0); // 添加数据到一层的列表中 levelArray.add(temp.val); // sout(temp.val) // pre--; count--; if(temp.left!=null){ list.addLast(temp.left); count++; } if(temp.right!=null){ list.addLast(temp.right); count++;; } //保存一层的节点数, if(pre==0) { pre=count; retArray.add(levelArray); if(list.size()>0) levelArray=new ArrayList<Integer>(); } } return retArray; } }