目录
题目描述:
代码:
第一种:
第二种:
TreeNode:
LinkedListNode:
题目描述:
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
代码:
第一种:
LinkedListQueue<TreeNode> queue = new LinkedListQueue<TreeNode>();queue.offer(root);int c1=1;//当前的节点数while(!queue.isEmpty()){int c2=0;for(int i=0;i<c1;i++){TreeNode n=queue.poll();System.out.print(n+" ");if(n.left!=null){queue.offer(n.left);c2++;}if(n.right!=null){queue.offer(n.right);c2++;}}System.out.println();c1=c2;}第二种:
public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer> > res = new ArrayList<>();if(root==null) return res;LinkedListQueue<TreeNode> queue = new LinkedListQueue<TreeNode>();queue.offer(root);int c1=1;//当前的节点数while(!queue.isEmpty()){List<Integer> level=new ArrayList<>();int c2=0;for(int i=0;i<c1;i++){TreeNode n=queue.poll();level.add(n.val);if(n.left!=null){queue.offer(n.left);c2++;}if(n.right!=null){queue.offer(n.right);c2++;}}res.add(level);c1=c2;}return res;}TreeNode:
package TreeNode;public class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int val){this.val = val;}public TreeNode( TreeNode left,int val, TreeNode right){this.val = val;this.left = left;this.right = right;}public String toString(){return String.valueOf(val);}}LinkedListNode:
public class LinkedListQueue <E> implements Queue<E>, Iterable<E>{//单向环形哨兵链表//节点类private static class Node<E>{E value;Node<E> next;Node(E value, Node<E> next){this.value=value;this.next=next;}}Node<E> head=new Node<>(null,null);Node<E> tail=head;//tail指向头private int size=0;//节点数private int capacity=Integer.MIN_VALUE;//容量public LinkedListQueue(){tail.next=head;}public LinkedListQueue(int capacity){this.capacity=capacity;tail.next=head;}//从队尾插入@Overridepublic boolean offer(E value) {if(isFull()){return false;}Node<E> added= new Node<>(value,head);//added新节点尾部指向头tail.next=added;//原来的尾部指向新节点tail=added;//尾部指向新节点size++;return true;}//获取队列的第一个值,并移除@Overridepublic E poll() {if(isEmpty()){return null;}E value=head.next.value;Node<E> first=head.next;head.next=first.next;size--;if(first==tail){tail=head;}return value;}//从对头获取值,但不移除@Overridepublic E peek() {if(isEmpty()){return null;}return head.next.value;}@Overridepublic boolean isEmpty() {return head==tail;}@Overridepublic boolean isFull() {return size==capacity;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>(){Node<E> p=head.next;public boolean hasNext() {//p==head退出return p!=head;}public E next(){E value=p.value;p=p.next;return value;}};}}
