二叉树的广度优先遍历
public class Solution { public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<Integer> res=new ArrayList(); LinkedList<TreeNode> queue=new LinkedList(); if(root==null){ return res; } queue.add(root); while(!queue.isEmpty()){ TreeNode temp=queue.removeFirst(); res.add(temp.val); if(temp.left!=null){ queue.add(temp.left);} if(temp.right!=null){ queue.add(temp.right);} } return res; } }
在原有的基础上分开打印每层的节点,只需出队前判断记录当前的队列节点个数,循环出队即可
public class Solution { ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { LinkedList<TreeNode> link=new LinkedList(); ArrayList<ArrayList<Integer>> res=new ArrayList(); if(pRoot==null){ return res; } link.add(pRoot); while(!link.isEmpty()){ int size=link.size();//出队前判断当前层节点个数 ArrayList<Integer> list=new ArrayList();//存储当前层节点的集合 while(size>0){ TreeNode node=link.removeFirst();//出队 list.add(node.val); size--; if(node.left!=null){//入队当前节点左右子节点 link.add(node.left); } if(node.right!=null){ link.add(node.right); } } res.add(list); } return res; } }