从上到下打印二叉树
题目描述
思路
队列
这个其实是树的基本操作之一，层序遍历，也叫广度优先遍历，可以通过队列的先进先出来实现
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
public int[] levelOrder(TreeNode root) {
List<Integer> result=new ArrayList<Integer>();
if (root==null){
return new int[0];
}
queue.offer(root);
while(!queue.isEmpty()){
TreeNode cur=queue.poll();
result.add(cur.val);
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
int[]r=new int[result.size()];
for(int i=0;i<r.length;i++){
r[i]=result.get(i);
}
return r;
}
}
复杂度分析
时间复杂度
O(N)
空间复杂度
O(N)，首先有List，而且满二叉树的情况下，会有N/2个元素在队列里面
反思不足
java se
Queue
- LinkedList实现了Queue接口，所以可以直接用这个类实例化
此外还有isEmpty用于判断是否为空,toArray返回的是Object数组，无法转化为int[]
ArrayList
从上到下打印二叉树II
题目描述
思路
双队列
将当前层与下层元素保存在两个队列中，分别出队封装
队列+size()
通过size获取当前层的个数，以之区分两层
代码实现
双队列
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Queue<TreeNode>cur = new LinkedList<TreeNode>();
Queue<TreeNode>next = new LinkedList<TreeNode>();
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> r = new ArrayList<List<Integer>>();
if(root==null){
return new ArrayList<List<Integer>>();
}
cur.offer(root);
List<Integer> item = new ArrayList<Integer>();
while(!cur.isEmpty()||!next.isEmpty()){
TreeNode n=cur.poll();
item.add(n.val);
if(n.left!=null){
next.offer(n.left);
}
if(n.right!=null){
next.offer(n.right);
}
if(cur.isEmpty()){
cur=next;
next=new LinkedList<TreeNode>();
r.add(item);
item=new ArrayList<Integer>();
}
}
return r;
}
}
队列+size()
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Queue<TreeNode>cur = new LinkedList<TreeNode>();
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> r = new ArrayList<List<Integer>>();
if(root==null){
return new ArrayList<List<Integer>>();
}
cur.offer(root);
List<Integer> item = new ArrayList<Integer>();
while(!cur.isEmpty()){
for(int i=cur.size();i>0;i--){
TreeNode n=cur.poll();
if(n.left!=null){
cur.offer(n.left);
}
if(n.right!=null){
cur.offer(n.right);
}
item.add(n.val);
}
r.add(item);
item = new ArrayList<Integer>();
}
return r;
}
}
复杂度分析
时间复杂度
二者的本质还是层序遍历，O(N)
空间复杂度
均为O(N)，但前者还是要高一点的
反思不足
思路
一开始想的是两个队列，一个存放当前层的一个存放下一层的，然后发现可行
看了题解之后，发现一个队列也可以完成，用size得到当前层的元素个数，然后设置一个for循环
我当时想的是如何能区分出两层，而没有往当前层有多少个的角度去想，也没有想过可以用这种方式区分
从上到下打印二叉树III
题目描述
思路
队列+栈+计数器
自己想的方法，算是学有所用
双端队列+计数器
双端队列的特点在于极端情况下两边皆可入队出队，于是就可以奇数的时候队头入队，偶数的时候队尾入队
这里的双端队列是指结果集
双端队列+奇偶判断逻辑分离
对上一种方法的优化，取消了判断当前是奇数层还是偶数层
如何分离？首先在队列中的元素都得是跟普通层序遍历一个次序，于是乎打印偶数层添加时就得从右往左加子元素，在打印奇数层时从前往后删，偶数层从后往前删，用for循环记录开始的元素个数以区分层与层
每轮都打印两层
这里的双端队列是指每层元素
队列+倒序+返回结果集size
对第一种方法的优化
用返回结果集size判断当前是奇数层还是偶数层
直接调用Collections.reverse(tmp)完成内部元素的逆置，而不用使用栈
代码实现
队列+计数器+栈
class Solution {
Queue<TreeNode> cur = new LinkedList<TreeNode>();
Stack<Integer> stack = new Stack<Integer>();
public List<List<Integer>> levelOrder(TreeNode root) {
int cth = 1;
List<List<Integer>> r = new ArrayList<List<Integer>>();
if (root == null) {
return new ArrayList<List<Integer>>();
}
cur.offer(root);
List<Integer> item = new ArrayList<Integer>();
while (!cur.isEmpty()) {
//代码有很大程度上的冗余
if (cth % 2 != 0) {
for (int i = cur.size(); i > 0; i--) {
TreeNode n = cur.poll();
if (n.left != null) {
cur.offer(n.left);
}
if (n.right != null) {
cur.offer(n.right);
}
item.add(n.val);
}
}else{
for (int i = cur.size(); i > 0; i--) {
TreeNode n = cur.poll();
if (n.left != null) {
cur.offer(n.left);
}
if (n.right != null) {
cur.offer(n.right);
}
stack.push(n.val);
}
while(!stack.empty()){
item.add(stack.pop());
}
}
r.add(item);
cth++;
item = new ArrayList<Integer>();
}
return r;
}
}
双端队列+计数器
class Solution {
Queue<TreeNode> cur=new LinkedList<TreeNode>();
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> r=new ArrayList<List<Integer>>();
if(root!=null){
cur.offer(root);
}
int cth=1;
while(!cur.isEmpty()){
LinkedList<Integer> item=new LinkedList<Integer>();
for(int i=cur.size();i>0;i--){
TreeNode n=cur.poll();
if(n.left!=null){
cur.offer(n.left);
}
if(n.right!=null){
cur.offer(n.right);
}
if(cth%2==1){
item.addLast(n.val);
}else{
item.addFirst(n.val);
}
}
r.add(item);
cth++;
}
return r;
}
}
双端队列+奇偶判断逻辑分离
class Solution {
Deque<TreeNode> cur = new LinkedList<TreeNode>();
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> r = new ArrayList<List<Integer>>();
if (root == null) {
return new ArrayList<List<Integer>>();
}
cur.offer(root);
while (!cur.isEmpty()) {
//打印奇数层
List<Integer> item = new ArrayList<Integer>();
for (int i = cur.size(); i > 0; i--) {
TreeNode n = cur.removeFirst();
if (n.left != null) {
cur.addLast(n.left);
}
if (n.right != null) {
cur.addLast(n.right);
}
item.add(n.val);
}
r.add(item);
//打印偶数层
if(cur.isEmpty()){
break;
}
item = new ArrayList<Integer>();
for(int i=cur.size();i>0;i--){
TreeNode n = cur.removeLast();
if (n.right != null) {
cur.addFirst(n.right);
}
if (n.left != null) {
cur.addFirst(n.left);
}
item.add(n.val);
}
r.add(item);
}
return r;
}
}
队列+倒序+返回结果集size
class Solution {
Queue<TreeNode> cur = new LinkedList<TreeNode>();
public List<List<Integer>> levelOrder(TreeNode root) {
int cth = 1;
List<List<Integer>> r = new ArrayList<List<Integer>>();
if (root == null) {
return new ArrayList<List<Integer>>();
}
cur.offer(root);
List<Integer> item = new ArrayList<Integer>();
while (!cur.isEmpty()) {
//代码有很大程度上的冗余
for (int i = cur.size(); i > 0; i--) {
TreeNode n = cur.poll();
if (n.left != null) {
cur.offer(n.left);
}
if (n.right != null) {
cur.offer(n.right);
}
item.add(n.val);
}
if(r.size()%2==1){
Collections.reverse(item);
}
r.add(item);
cth++;
item = new ArrayList<Integer>();
}
return r;
}
}
复杂度分析
时间复杂度
均为O(N)
空间复杂度
均为O(N)
反思不足
思路
在上一题的基础上，想到用计数器加栈的方式实现，可行，而且效率不错
该思路的代码可以优化，冗余太多
优化方法就是利用双端队列
java se
Collections
有关api：
- Collections.reverse(tmp)可完成对内部元素的逆置
Deque
双端队列所实现的接口
有关api：
addFirst
addLast
removeFirst
removeLast
LinkedList
标签：TreeNode,cur,offer,ArrayList,day06,item,new,null From： https://www.cnblogs.com/zhouj-learn/p/16779384.html该类可做双端队列使用