$$\color{Red}{二叉树的锯齿形层次遍历【leetcode103 bfs变体】}$$

我的网站=> 分享了我关于前后端的各种知识和生活美食~

我于Acwing平台分享的零散刷的各种各样的题

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -100 <= Node.val <= 100

解析

和二叉树层序遍历的区别就是，每进入下一层数据要从头插法和尾插法进行切换。

最节省代码量的就是加一个标志位，然后存每一层靠标志位决定当层答案是头插法存还是尾插法存，这样不需要进行链表反转操作。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        boolean zigzag = true;
        LinkedList<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            int len = q.size();
            LinkedList<Integer> level = new LinkedList<>();
            while (len --> 0) {
                TreeNode t = q.remove();
                if (zigzag) level.add(t.val);
                else level.push(t.val);
                if (t.left != null) q.add(t.left);
                if (t.right != null) q.add(t.right);
            }
            zigzag = !zigzag;
            ans.add(new ArrayList<>(level));           
        }
        return ans;
    }
}