详解java实现遍历二叉树的三种情况
遍历二叉树,从上往下遍历。但是同层节点可以从左向右遍历,也可以从右向左遍历(也就是之字型遍历),其中,都需要队列进行实现。只是按照之字型稍微麻烦一些。
(1)从上往下打印出二叉树的每个节点,同层节点从左至右打印。
需要一个队列,队列里面放节点(从根节点开始),然后依次进行打印。
importjava.util.ArrayList; importjava.util.Queue; importjava.util.LinkedList; classTreeNode{ intval=0; TreeNodeleft=null; TreeNoderight=null; publicTreeNode(intval){ this.val=val; } } publicclassSolution{ publicArrayListPrintFromTopToBottom(TreeNoderoot){ ArrayList list=newArrayList (); if(root==null) returnlist; Queue queue=newLinkedList (); queue.add(root); while(!queue.isEmpty()){ TreeNodet=queue.poll(); list.add(t.val); if(t.left!=null)queue.add(t.left); if(t.right!=null)queue.add(t.right); } returnlist; } }
(2)请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
解析:之字形打印二叉树,不要将所有层放入ArrayList中后再将偶数层进行reverse(),这样可以实现,但是数据量大的时候效率太低。
importjava.util.ArrayList; importjava.util.LinkedList; importjava.util.Queue; classTreeNode{ intval=0; TreeNodeleft=null; TreeNoderight=null; publicTreeNode(intval){ this.val=val; } } publicclassSolution{ publicArrayList>Print(TreeNodepRoot){ ArrayList >result=newArrayList >(); if(pRoot==null){ returnresult; } Queue queue=newLinkedList (); introws=1; queue.add(pRoot); while(!queue.isEmpty()){ ArrayList list=newArrayList(); intsize=queue.size(); for(inti=0;i (3)从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
这道题就是典型的二叉树层次遍历。
思路:因为我们要按层打印,所以需要设置标志量。
其次:我们需要三个集合:
第一个集合用于存放结果集
第二个集合用于临时存放每一层的结果,等到一层结束之后,再将其加入到最终结果集中。注意,每一次使用完这个集合之后,需要将其清空,以便下一次存放。
第三个集合用于存放节点。
importjava.util.ArrayList; importjava.util.LinkedList; importjava.util.*; classTreeNode { intval=0; TreeNodeleft=null; TreeNoderight=null; publicTreeNode(intval) { this.val=val; } } publicclassSolution { ArrayList>Print(TreeNodepRoot) { ArrayList >result=newArrayList >(); ArrayList arrayList=newArrayList (); Queue queue=newLinkedList ();//存放节点 //检查是否为空 if(pRoot==null) returnresult; queue.add(pRoot); intstart=0; intend=1;//第一行 while(!queue.isEmpty()) { TreeNodetreeNode=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(newArrayList (arrayList));//加入结果集中 arrayList.clear();//必须将临时存放结果的集合清空,以便进行下一次存放 end=start;//恢复原状 start=0; } } returnresult; } } 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。