这个题一看就发现，这不是层序遍历吗？
虽然不太记得写法了，但回忆了一下，基本上很快就用队列实现了
问题是好多java的基础知识反倒不是很熟，写错了好多地方
思路如下：
代码如下：
class Solution { public int[] levelOrder(TreeNode root) { List<Integer> result=new ArrayList<>(); if(root==null) {return new int[0];}//这一步或许可以归到里面 Queue<TreeNode> queue=new ArrayDeque<TreeNode>(); queue.add(root); while(queue.size()!=0) { root=queue.poll(); result.add(root.val); if(root.left!=null) {queue.add(root.left);} if(root.right!=null) {queue.add(root.right);} } int[] realResult=new int[result.size()]; for(int i=0;i<result.size();i++) {realResult[i]=result.get(i).intValue();} return realResult; } }
来看一下写的过程中遇到的基础问题：
- 直接返回一个空数组（数组的new方式）
- Queue的new方式
- queue的增删改查（add和poll）
- arraylist的增删改查
- 如何把不定长arraylist转为数组，尤其是在泛型为Integer时
1.数组有几种常见的new方式
int[] a=new int[0];//创建指定长度数组 int[] b={1,2,3};//直接按元素创建数组，大括号注意
2.Queue的new方式
队列分类：
按照实现方式：
（1）单向队列（Queue）:只能在一端插入数据，在另一端删除数据。
（2）双向队列（Deque）:每一端都可以进行插入数据和删除数据操作。
（3）优先级队列：优先级队列是比栈和队列更专用的数据结构，在优先级队列中，数据项按照关键字进行排序，关键字最小（或者最大）的数据项往往在队列的最前面，而数据项在插入的时候都会插入到合适的位置以确保队列的有序。
Queue<TreeNode> queue=new LinkedList<>();
通常情况下，队列有数组和链表两种实现方式。
单向队列最常见的实现类是LinkedList
https://zhuanlan.zhihu.com/p/33920511
3.Queue的增删改查
public interface Queue<E> extends Collection<E> { //插入元素，成功返回true，失败抛出异常 boolean add(E e); //插入元素，成功返回true，失败返回false或抛出异常 boolean offer(E e); //取出并移除头部元素，空队列抛出异常 E remove(); //取出并移除头部元素，空队列返回null E poll(); //取出但不移除头部元素，空队列抛出异常 E element(); //取出但不移除头部元素，空队列返回null E peek(); }
我们用add和poll就行了
Queue 作为先进先出队列，只能从头部取元素、插入元素到尾部。Java 同样定义了双向队列 Deque，可以同时在头部、尾部插入和取出元素
public interface Deque<E> extends Queue<E> { //插入元素到队列头部，失败抛出异常 void addFirst(E e); //插入元素到队列尾部，失败抛出异常 void addLast(E e); //插入元素到队列头部，失败返回false或抛出异常 boolean offerFirst(E e); //插入元素到队列尾部，失败返回false抛出异常 boolean offerLast(E e); //取出并移除头部元素，空队列抛出异常 E removeFirst(); //取出并移除尾部元素，空队列抛出异常 E removeLast(); //取出并移除头部元素，空队列返回null E pollFirst(); //取出并移除尾部元素，空队列返回null E pollLast(); //取出但不移除头部元素，空队列抛出异常 E getFirst(); //取出但不移除尾部元素，空队列抛出异常 E getLast(); //取出但不移除头部元素，空队列返回null E peekFirst(); //取出但不移除尾部元素，空队列返回null E peekLast(); //移除指定头部元素，若不存在队列不变，移除成功返回true boolean removeFirstOccurrence(Object o); //移除指定尾部元素，若不存在队列不变，移除成功返回true boolean removeLastOccurrence(Object o); //单向队列方法，参考Queue //栈方法，参考栈 //集合方法，参考集合定义 }
4.arraylist的增删改查
List<Integer> list=new ArrayList<>();//new list.add(1);//增 list.remove(0);//按照索引删除，返回删除的值 list.add(200); list.remove(new Integer(200));//删除可按照内容删除 list.add(100); list.set(0,50);//改 System.out.println(list.get(0));//查
老直接写成list[0]这种，傻了
5.如何把不定长arraylist转为数组，尤其是在泛型为Integer时
如果泛型中是String这种类型就很好说，直接toArray就行
String[] array=new String[list.size()];//类型和数组大小 list.toArray(array);
如果是Integer就不能直接转int[]了，只能挨个复制了
int[] realResult=new int[result.size()]; for(int i=0;i<result.size();i++) {realResult[i]=result.get(i).intValue();}
看来包装类还得好好看一看
上一次做的层序的题目出来的结果要是分层的，那个就是每次对队列进行计数再poll