LeetCode103 BinaryTreeZigzagLevelOrderTraversal(二叉樹Z形層次遍歷) Java題解

LeetCode103 BinaryTreeZigzagLevelOrderTraversal(二叉樹Z形層次遍歷) Java題解

題目：

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

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

    3
   / 
  9  20
    /  
   15   7

return its zigzag level order traversal as:

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

解題：

這題其實和二叉樹的層序遍歷很類似 僅僅是在這個基礎上加上一個左右方向 一開始我的思維被局限住了 寫了一個很冗余的代碼版本 實現思路是這樣的 當需要從右到左輸出的時候 我把隊列裡面的節點輸出然後 反序存回隊列

代碼：

public static List> zigzagLevelOrder(TreeNode root) {
		
		List> result=new ArrayList>();//存放最終結果
		boolean isLeftToRight=false;//從左到右的方向
		Queue nodeQueue=new LinkedList<>();//存放節點 便於每一層遍歷
		
		
		//處理根節點
		if(root==null)
			return result;
		else {
			List list=new ArrayList<>();
			list.add(root.val);
			result.add(list);
			nodeQueue.offer(root);
		}
		
		while(!nodeQueue.isEmpty())
		{
			int size=nodeQueue.size();
			List tempResult=new ArrayList<>();//用來暫時存放每一層節點的遍歷結果
			
			Stack stack=new Stack<>();//用來輔助將隊列倒序
			
			if(isLeftToRight)
			{
				//將隊列裡面的節點都先出隊列進棧再出棧進隊列  使得和原來的順序剛好相反
				for(int i=0;i0)//從左到右
				{
					size--;
					TreeNode tempNode=nodeQueue.poll();
					if(tempNode.left!=null)
					{
						nodeQueue.offer(tempNode.left);
						tempResult.add(tempNode.left.val);
					}
					if(tempNode.right!=null)
					{
						nodeQueue.offer(tempNode.right);
						tempResult.add(tempNode.right.val);
					}
				}
				
				if(!tempResult.isEmpty())  result.add(tempResult);
				//循環退出 表示一層已經遍歷完了  這時候重置方向標志位
				isLeftToRight=false;
				
			}
			else {
				//將隊列裡面的節點都先出隊列進棧再出棧進隊列  使得和原來的順序剛好相反
				for(int i=0;i0)//從右到左
				{
					size--;
					TreeNode tempNode=nodeQueue.poll();
					if(tempNode.right!=null)
					{
						nodeQueue.offer(tempNode.right);
						tempResult.add(tempNode.right.val);
					}
					if(tempNode.left!=null)
					{
						nodeQueue.offer(tempNode.left);
						tempResult.add(tempNode.left.val);
					}
				}
				if(!tempResult.isEmpty())  result.add(tempResult);
				//循環退出 表示一層已經遍歷完了  這時候重置方向標志位
				isLeftToRight=true;
			}
		}
		
		return result;
		
        
    }

public static List> zigzagLevelOrder2(TreeNode root) {
		
		List>  result=new ArrayList>();//存放最終結果
 		Queue nodeQueue=new LinkedList<>();//存放節點
		int flag=1;//flag為奇數的時候 從左到右  為偶數的時候從右到左；
		
		if(root==null)
			return result;
		else {
			nodeQueue.add(root);
		}
		
		while(!nodeQueue.isEmpty())
		{
			int count=nodeQueue.size();
			List tempResult=new ArrayList<>();
			while(count>0)
			{
				TreeNode tempNode=nodeQueue.poll();
				count--;
				if(flag%2!=0)//從左到右
				{
					tempResult.add(tempNode.val);
				}
				else {//
					tempResult.add(0,tempNode.val);
				}
				
				if(tempNode.left!=null)
					nodeQueue.add(tempNode.left);
				if(tempNode.right!=null)
					nodeQueue.add(tempNode.right);
			}
			if(!tempResult.isEmpty()) result.add(tempResult);
			flag++;
		}
		
		return result;
		
	
	}

}