题解 | #二叉树的之字形层序遍历#

题目：二叉树的之字形层序遍历

描述：给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如：给定的二叉树是{3,9,20,#,#,15,7},

该二叉树之字形层序遍历的结果是[ [3], [20,9], [15,7] ]

示例1：输入：{1,#,2}，返回值：[[1],[2]]

解法一：

思路分析：因为是要将二叉树进行之字形层序遍历，所以我们采用双栈进行，排序规则为第一层通过正序输出，第二层逆序输出，第三层正序输出，通过依次类推，实现之字形排序，使用栈的性质（先进后出），先进入栈的数据最后再出栈，为了能够实现逆序遍历，将二叉树的第二层结点保存在栈1中，重新设置栈2存储下一层结点，使用stackout表示存储当前层结点的栈。stackIn表示存储下一层节点的栈，从左往右遍历(正向遍历)时，需要存储当前节点的左节点stackIn中；从右往左遍历(反向遍历)时，需要存储当前节点的右节点stackIn中

实例分析：以二叉树{3,9,20,#,#,15,7}为例，将根节点3存入stack1中，首先遍历的方向为从左往右遍历，其中stack1为stackout，stack2为stackin，当遍历完成后，stack1为空，stack2中存储着第二层的结点，遍历时需要不断pop出stackout中的结点，添加到arraylist中，从而可以得到第一层的顺序遍历。

当遍历完第一层后，将方向反转，变为从右往左遍历，此时stack2为stackout，stack1为stackin，遍历完成后stack2为空，stack1中存储着第三层的结点，还是需要不断的pop出stackout中的结点，添加到arraylist中，得到第二层的逆序遍历。

依次类推，返回最终值[ [3], [20,9], [15,7] ]。

Java代码为：

import java.util.*;
 
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
 
public class Solution {
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList<arraylist><>>
     */
    public ArrayList zigzagLevelOrder (TreeNode root) {
        // write code here
        ArrayList cache = new ArrayList<>();
        if(root == null)
            return cache;
        Deque stack1 = new LinkedList<>();//设置双栈
        Deque stack2 = new LinkedList<>();
        stack1.push(root);//将根节点压入栈1
        boolean isfound = true;//设置方向
        
        while(stack1.isEmpty() == false || stack2.isEmpty() == false){//当前栈是否还有元素
            DequestackOut = stack1.isEmpty() ? stack2 : stack1;
            DequestackIn = stack1.isEmpty() ? stack1 : stack2;
            //stackout存储当前层，stackin存储下一层
            cache.add(new ArrayList<>());
            //遍历当前层的结点
            while(stackOut.isEmpty() == false){
                //栈顶出栈
                TreeNode cur = stackOut.pop();
                //添加到Arraylist里边
                cache.get(cache.size() - 1).add(cur.val);
                if (isfound) {
                    //如果方向是从左往右，则先遍历当前节点的左节点
                    pushNode(stackIn, cur.left);
                    pushNode(stackIn, cur.right);
                }
                else {
                    //如果方向是从右往左，则先遍历当前节点的右节点
                    pushNode(stackIn, cur.right);
                    pushNode(stackIn, cur.left);
                }
            }
            isfound = !isfound;//改变方向
        }
        return cache;
    }
    
    private void pushNode(Dequestack, TreeNode node) {//将结点存入栈中
        if (node != null) {
            stack.push(node);
        }
    }
}</arraylist>

遍历树中的每一个元素，时间复杂度为O(N)，空间复杂度为O(N)。

解法二：

思路分析：首先创建队列，将结点加入到队列当中，利用先进先出原则，依次弹出栈。将每次弹出结点的值保存到链表当中，如果是奇数层的话，就采用尾插，如果为偶数层的话，执行头插，如果弹出的结点中有左右子树，则将左右子结点加入到当前队列当中，在每一层遍历完成后都要将这一层的结点加入到链表当中。

具体Java代码为：

import java.util.*;
 
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
public class Solution {
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList<arraylist><>>
     */
    public ArrayList zigzagLevelOrder (TreeNode root) {
        ArrayList res = new ArrayList<>();
        Queueque = new LinkedList<>();//创建队列
        if(root != null){
            que.add(root);
        }
        while(!que.isEmpty()){
            ArrayListtmp = new ArrayList<>();//存储每一层节点
            for(int i = que.size();i > 0;i--){//遍历当前层的节点
                TreeNode node = que.poll();//弹出队列中的节点
                if((res.size() + 1) % 2 != 0){
                    tmp.add(node.val);//奇数尾插
                }
                else{
                    tmp.add(0,node.val);//偶数层头插
                }
                if(node.left!=null){//如果左子节点不为空，则将其加入到队列中
                    que.add(node.left);
                }
                if(node.right!=null){//如果右子节点不为空，则将其加入到队列中
                    que.add(node.right);
                }
            }
            res.add(tmp);//将这一层的节点加入到res中
        }
        return res;
    }
}</arraylist>

其时间复杂度为O(N)，设置链表对象和队列用与存储数字，所以其空间复杂度为O(N)。