描述

题目描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

示例

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

知识点：二叉树，队列，栈，BFS
难度：⭐⭐⭐

题解

解题思路

一旦看到这种有关顺序的，第一个就要想到用栈或队列实现，有这个思路才能进一步实现、优化。

比如这道题，要求 “第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印”，显然，如果能直接利用栈或队列的特性，就能实现题目要求的各种顺序了。

方法一：双栈

图解

算法流程：

• 维护两个栈，一个存放奇数层的节点，一个存放偶数层的节点
• 整型变量level表示当前遍历第几层，奇数则顺序打印，偶数逆序打印, 从第1层开始
• 分奇数层和偶数层处理
  • 奇数层按顺序，每次偶数层的栈保存偶数层节点，先存左结点，这样等下次pop时就是右节点先打印
  • 偶数层反序，每次奇数层的栈保存偶数层节点，先存右结点，这样等下次pop时就是左节点先打印

Java 版本代码如下：

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(pRoot == null) {
            return res;
        }
        // 存放奇数层的节点
        Stack<TreeNode> stack1 = new Stack<>();
        stack1.push(pRoot);
        // 存放偶数层的节点
        Stack<TreeNode> stack2 = new Stack<>();
        // 表示当前遍历第几层，奇数则顺序打印，偶数逆序打印, 从第1层开始
        int level = 1; 
        while(!stack1.isEmpty() || !stack2.isEmpty()) {
            // 处理奇数层
            if(level % 2 != 0) {
                ArrayList<Integer> list = new ArrayList<>();
                // 奇数层按顺序
                while(!stack1.isEmpty()) {
                    TreeNode node = stack1.pop();
                    if(node != null) {
                        // 收集打印结果
                        list.add(node.val);
                        // stack2保存偶数层节点，先存左结点，这样等下次pop时就是右节点先打印，满足题目要求
                        stack2.push(node.left);
                        stack2.push(node.right);
                    }
                }
                // 收集当前层的结果
                if(!list.isEmpty()) {
                    res.add(list);
                    level++;
                }                 
            } else {
                // 处理偶数层
                ArrayList<Integer> list = new ArrayList<>();        
                while(!stack2.isEmpty()) {
                    TreeNode node = stack2.pop();
                    if(node != null) {
                        list.add(node.val);
                        // 需要按顺序push，因为stack1是用在奇数层按顺序输出结果的
                        stack1.add(node.right);
                        stack1.add(node.left);
                    }
                }
                if(!list.isEmpty()) {
                    res.add(list);
                    level++;
                }
            }
        }        
        return res;
    }
}

Python 版本代码如下：

class Solution:
    def zigzagLevelOrder(self, pRoot):
        if pRoot==None:
            return []
        stack1=[pRoot]
        stack2=[]
        res1=[]
        res2=[]
        result=[]
        while stack1 or stack2:
            res1=[]
            res2=[]
            # 处理奇数层
            while stack1:
                node=stack1.pop()
                # 按顺序，先存左节点，再存右节点
                if node.left:
                    stack2.append(node.left)
                if node.right:
                    stack2.append(node.right)
                res1.append(node.val)
            # 收集当前层的结果
            if len(res1)!=0:
                result.append(res1)
            # 处理偶数层
            while stack2:
                node=stack2.pop()
                if node.right:
                    stack1.append(node.right)
                if node.left:
                    stack1.append(node.left)
                res2.append(node.val)
            # 收集当前层的结果
            if len(res2)!=0:
                result.append(res2)
        return result

复杂度分析：

时间复杂度 O(N)：遍历树的每个结点N
空间复杂度 O(N)：题目要求返回的二维列表，不算是额外空间，但栈和List都是需要借助的额外空间

方法二：队列&双向遍历

算法流程：

• 维护一个双向队列，用于保存当前层的元素
• 每一层，队列都线加入null，表示每一层的分割点，同事用布尔值遍历表示当前方向是否是从左向右遍历的
• 进行双向遍历，直到队列中只有分隔符null
• 遇到层分隔符，表示当前已经在新的一层，接着通过迭代器和反向迭代器，进行每一层遍历结果的收集

Java 版本代码如下：

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer> > zigzagLevelOrder(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot == null) {
            return res;
        }
        ArrayList<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        // null表示每一层的分割点
        queue.offer(null);
        queue.offer(pRoot);
        // 当前方向是否是从左向右遍历的，第一层是从左往右的
        boolean toRight = true;
        // 双向遍历，直到队列中只有分隔符null
        while (queue.size() != 1) {
            TreeNode node = queue.poll();
            // 遇到层分隔符，表示当前已经在新的一层
            if (node == null) {
                Iterator<TreeNode> iter = null;
                // 从左往右遍历，从queue的头部元素开始迭代
                if (toRight) {
                    iter = queue.iterator();
                } else {
                    // 从右往左遍历，获取queue的尾部元素的迭代器
                    iter = queue.descendingIterator();
                }
                // 下次遍历的方向要反过来
                toRight = !toRight;
                // 遍历当前层结点，并收集当前层的结果
                while (iter.hasNext()) {
                    TreeNode temp = (TreeNode)iter.next();
                    list.add(temp.val);
                }
                // 保存每一层的结果
                res.add(new ArrayList<Integer>(list));
                list.clear();
                //添加层分隔符
                queue.offer(null);
                // 注意:例如每次遍历到这里，此时Queue队头元素还是当前层的第一个结点，上面只是poll掉分隔符null
                continue;
            }
            // 队列加入下一层的每个结点
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return res;
    }
}

复杂度分析：

时间复杂度 O(N)：遍历每个结点
空间复杂度 O(N)：有借助到队列实现双向遍历