LeetCode103. 二叉樹的鋸齒形層次周遊

給定一個二叉樹，傳回其節點值的鋸齒形層次周遊。（即先從左往右，再從右往左進行下一層周遊，以此類推，層與層之間交替進行）。

例如：

給定二叉樹 

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

,

3
   / \
  9  20
    /  \
   15   7
      

傳回鋸齒形層次周遊如下：

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

思路：在廣度優先周遊過程中，臨時存儲每一層的值，每隔一次将每一層的值順序倒置一下即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        
        List<List<Integer>> res=new LinkedList<List<Integer>>();//結果集
        if(null==root){
            return res;
        }
        ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();//輔助資料結構用于周遊樹
        queue.add(root);
        int count=0;
        while(!queue.isEmpty()){
            int size=queue.size();
            ArrayDeque<Integer> stack=new ArrayDeque<Integer>(); //臨時存儲每一層的值
            while(size>0){
                TreeNode node=queue.removeFirst();
                stack.push(node.val);
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
                size--;
            }
            if(count%2==0){//判定是否需要反轉
                List<Integer> tmp=reverseStack(stack);
                res.add(tmp);
            }else{
                List<Integer> tmp=new LinkedList<Integer>(stack);
                res.add(tmp);
            }
            count++;
        }
        return res;
    }
     /**
     * 反轉stack
     * @param stack
     * @return
     */
    public  List<Integer> reverseStack(ArrayDeque<Integer> stack){
        List<Integer> res=new LinkedList<Integer>();
        Object[] a=  stack.toArray();
        for(int i=a.length-1;i>=0;i--){
            res.add((int)a[i]);
        }
        return res;
    }
}