给你二叉树的根节点 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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

层次遍历当然是使用队列实现。Queue在Java中是一个接口，接口下有add，offer，poll，peek等方法。LinkedList类实现了这个接口（常用的还有优先级队列PriorityQueue），所以我们在这里使用LinkedList，但我们并不直接将对象赋值给Queue接口，因为我们还希望使用List接口下的get、remove等方法。所以这里我们直接使用LinkedList<TreeNode>作为q的类型。

/**
 * 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) {
        LinkedList<TreeNode> q = new LinkedList<>();
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        q.add(root);
        int size = 1; boolean dir = true;
        while (size != 0) {
            for (int i = 0; i < size; i++) {
                addChild(q, q.get(i));
            }
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                if (dir) tmp.add(q.poll().val);
                else tmp.add(q.remove(size - i - 1).val);
            }
            ans.add(tmp);
            size = q.size(); dir = !dir;
        }
        return ans;
    }

    void addChild(Queue<TreeNode> q, TreeNode n) {
        if (n.left != null) q.add(n.left);
        if (n.right != null) q.add(n.right);
    }
}

算法中的dir对象表示当前遍历的方向。

复杂度

  • 时间复杂度：。
  • 空间复杂度：。