首页 > 代码库 > 二叉树的层序遍历

二叉树的层序遍历

2024-07-24 00:39:01   218人阅读

原题：

Given a binary tree, return the level order traversal of its nodes‘ values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   /   9  20
    /     15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

解题思路：先考虑最简单的情况，按照层序遍历的方式输出节点的值，也就是说不分别存储每一层的节点。基本思路就是：设置一个队列，并首先把根节点入队。1.当队列不为空时，把队首元素出队并打印输出；2.如果存在子节点则把左右子节点分别入队；循环1.2两步直到队列为空。程序如下：

<span style="font-size:18px;">private static void levelOrderTraversal(TreeNode root) {
	if(root == null){  
        return ;  
    }  
	LinkedList<TreeNode>nodeQueue=new LinkedList<TreeNode>();
	nodeQueue.add(root);
	
	while(!nodeQueue.isEmpty())
	{
		TreeNode anode=nodeQueue.poll();
		System.out.print(anode.val);
		
		if(anode.left!=null){nodeQueue.add(anode.left);   }
		if(anode.right!=null){nodeQueue.add(anode.right); }
	}
}</span>
上面的程序只考虑了最简单的情形，只需要按照层序遍历的顺序输出节点值，但是无法判断各个节点所在的层次。如果需要考虑层次问题，则要进一步改进。改进后的程序如下：

<span style="font-size:18px;">public static List<List<Integer>> levelOrder(TreeNode root) {
	
	List<List<Integer>> list=new ArrayList<List<Integer>>();  
	if(root == null){  
         return list;  
     }     
	LinkedList<TreeNode>nodeQueue=new LinkedList<TreeNode>();
	nodeQueue.add(root);	
	while(!nodeQueue.isEmpty())
	{
		TreeNode lastNode=nodeQueue.getLast();
		ArrayList<Integer> alist=new ArrayList<Integer>();
		
		while(nodeQueue.getFirst()!=lastNode)
		{
			TreeNode firstNode=nodeQueue.getFirst();
			alist.add(firstNode.val);
			if(firstNode.left!=null)nodeQueue.add(firstNode.left);
			if(firstNode.right!=null)nodeQueue.add(firstNode.right);
			nodeQueue.removeFirst();
		}
		alist.add(lastNode.val);
		if(lastNode.left!=null)nodeQueue.add(lastNode.left);
		if(lastNode.right!=null)nodeQueue.add(lastNode.right);
		nodeQueue.removeFirst();
		list.add(alist);
	}
	return list;     
   }</span>
可以看出，程序的思路还是差不多，不过这次是在大循环里面加入了另一个循环，这个循环用来处理每一层的节点。稍微改进则可以得到另一个程序：Binary Tree Zigzag Level Order Traversal，改进的思路是：增加一个变量来标志层次遍历的方向，如果该标志为false，那么说明是从左往右，在遍历该层节点时，把每个节点加入到List的尾部；如果该标志为true，那么说明是从右往左，在遍历该层节点时，把每个节点加入到List的首部。程序如下：

public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		
		List<List<Integer>> list=new ArrayList<List<Integer>>();  
		if(root == null){  
	         return list;  
	     }  
	    
		boolean rightToLeft=false;
		
		LinkedList<TreeNode>nodeQueue=new LinkedList<TreeNode>();
		nodeQueue.add(root);
		
		while(!nodeQueue.isEmpty())
		{
			TreeNode lastNode=nodeQueue.getLast();
			LinkedList<Integer> alist=new LinkedList<Integer>();
			
			while(nodeQueue.getFirst()!=lastNode)
			{
				TreeNode firstNode=nodeQueue.getFirst();
				if(rightToLeft)alist.addFirst(firstNode.val);
				else alist.addLast(firstNode.val);
				if(firstNode.left!=null)nodeQueue.add(firstNode.left);
				if(firstNode.right!=null)nodeQueue.add(firstNode.right);
				
				nodeQueue.removeFirst();
			}
			if(rightToLeft)alist.addFirst(lastNode.val);
			else alist.addLast(lastNode.val);
			
			if(lastNode.left!=null)nodeQueue.add(lastNode.left);
			if(lastNode.right!=null)nodeQueue.add(lastNode.right);
			nodeQueue.removeFirst();
			list.add(alist);
			
			rightToLeft=!rightToLeft;
		}
		return list;     
	   }



二叉树的层序遍历


联系
我们