遍历二叉树,从上往下遍历。但是同层节点可以从左向右遍历,也可以从右向左遍历(也就是之字型遍历),其中,都需要队列进行实现。只是按照之字型稍微麻烦一些。
(1)从上往下打印出二叉树的每个节点,同层节点从左至右打印。
需要一个队列,队列里面放节点(从根节点开始),然后依次进行打印。
import java.util.arraylist; import java.util.queue; import java.util.linkedlist; class treenode{ int val = 0; treenode left = null; treenode right = null; public treenode(int val){ this.val = val; } } public class solution { public arraylist<integer> printfromtoptobottom(treenode root) { arraylist<integer> list = new arraylist<integer>(); if(root == null) return list; queue<treenode> queue = new linkedlist<treenode>(); queue.add(root); while(!queue.isempty()){ treenode t = queue.poll(); list.add(t.val); if(t.left != null) queue.add(t.left); if(t.right != null) queue.add(t.right); } return list; } }
(2)请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
解析:之字形打印二叉树,不要将所有层放入arraylist中后再将偶数层进行reverse(),这样可以实现,但是数据量大的时候效率太低。
import java.util.arraylist; import java.util.linkedlist; import java.util.queue; 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 proot) { arraylist<arraylist<integer>> result=new arraylist<arraylist<integer>>(); if(proot==null){ return result; } queue<treenode> queue = new linkedlist<treenode>(); int rows=1; queue.add(proot); while(!queue.isempty()){ arraylist<integer> list=new arraylist(); int size=queue.size(); for(int i=0;i<size;i++){ treenode t=queue.poll(); if(rows%2==0){ list.add(0,t.val); //将元素插入指定位置(头部),也就相当于倒序了 }else{ list.add(t.val); //将元素插入尾部 } if(t.left!=null){ queue.offer(t.left); } if(t.right!=null){ queue.offer(t.right); } } result.add(list); rows++; } return result; } }
(3)从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
这道题就是典型的二叉树层次遍历。
思路:因为我们要按层打印,所以需要设置标志量。
其次:我们需要三个集合:
第一个集合用于存放结果集
第二个集合用于临时存放每一层的结果,等到一层结束之后,再将其加入到最终结果集中。注意,每一次使用完这个集合之后,需要将其清空,以便下一次存放。
第三个集合用于存放节点。
import java.util.arraylist; import java.util.linkedlist; import java.util.*; class treenode { int val = 0; treenode left = null; treenode right = null; public treenode(int val) { this.val = val; } } public class solution { arraylist<arraylist<integer>> print(treenode proot) { arraylist<arraylist<integer>> result = new arraylist<arraylist<integer>>(); arraylist<integer> arraylist = new arraylist<integer>(); queue<treenode> queue = new linkedlist<treenode>(); // 存放节点 // 检查是否为空 if (proot == null) return result; queue.add(proot); int start = 0; int end = 1; // 第一行 while (!queue.isempty()) { treenode treenode = queue.poll(); end--; arraylist.add(treenode.val); if (treenode.left != null) // 如果有左节点 { queue.add(treenode.left);// 将左节点加入linkedlist中 start++; // 标志进入下一行 } if (treenode.right != null) { queue.add(treenode.right); start++; // 标志进入下一行 } if (end == 0) { // 此时也就是说明把一层已经打印完了,应该将其加入结果集中 result.add(new arraylist<integer>(arraylist)); // 加入结果集中 arraylist.clear();// 必须将临时存放结果的集合清空,以便进行下一次存放 end = start; // 恢复原状 start = 0; } } return result; } }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持移动技术网。
如对本文有疑问, 点击进行留言回复!!
第三次学JAVA再学不好就吃翔(part88)--ArrayList嵌套ArrayList
使用ffmpeg视频切片并加密和视频AES-128加密后播放
JAVA程序设计:最长重复子串(LeetCode:1044)
LiveGBS国标GB/T28181云端录像分布式录像存储自动清理时移回看录像下载播放
网友评论