題目：
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;
}
後面看別人的解答，其實完全沒有必要在隊列中反序 只要在存每一層輸出結果的ArrayList中反序存入就可以了 下面是這種思路的代碼：
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;
}
}
看代碼的長度就知道我之前的有多復雜了
