从上到下打印二叉树

问题描述

不分行的从上到下打印二叉树的每个节点，同一层的结点按照从左到右的顺序打印

思路分析

其实也就是树的层次遍历，而层次遍历的通法就是构造一个队列或者其他容器集合，按照从上到下依次加进结点，每次删除一个结点，就把它的左右孩子结点加入队列，依次类推，这里使用list模拟层序遍历

码上有戏

class TreeNode{
	int data;
	TreeNode left;
	TreeNode right;
	
	TreeNode(int data){
		this.data=data;
	}
}

public List<Integer> printFromToptoButtom(TreeNode root){
		List<TreeNode> node=new ArrayList<TreeNode>();
		 List<Integer> treeDate=new ArrayList<Integer>();
		  int index=1;
		   if(root==null)
			   return null;
		      node.add(root);
		     while(node.size()>0){
		    	 TreeNode front=node.remove(0);
		    	   index--;
		    	   treeDate.add(front.data);
		    	   if(front.left!=null)
		    	   {
		    		   node.add(index++,front.left);
		    		  
		    	   }
		    	   if(front.right!=null){
		    		   node.add(index++,front.right);		  
		    	   }
		     }
		     return treeDate;
	}

	public static void main(String[] args) {
       TreeNode a=new TreeNode(1);
       TreeNode b=new TreeNode(2);
       TreeNode c=new TreeNode(3);
       TreeNode d=new TreeNode(4);
       TreeNode e=new TreeNode(5);
       a.left=b;
       a.right=c;
       b.left=e;
       b.right=null;
       c.right=d;
       c.left=null;
       d.left=null;
       d.right=null;
       e.left=null;
       e.right=null;
      List<Integer> data= new ConstructBinaryTree().printFromToptoButtom(a);
       for(Integer h:data){
    	   System.out.print(h+" ");
       }
   
	}