103. 二叉树的锯齿形层序遍历

机会总是垂青有准备的人。

参考103. 二叉树的锯齿形层序遍历。

题目

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

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

解题思路

• 广度优先搜索：题目结果分层,考虑使用bfs进行层序遍历,同时维护队列的访问顺序和添加顺序。

广度优先搜索

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //考虑bfs
        List<List<Integer>> ans = new ArrayList<>();
        LinkedList<TreeNode> q = new LinkedList<>();
        if(root != null) q.add(root);
        boolean flag = true;//方向是否为左到右
        while(q.size() > 0) {
            List<Integer> list = new ArrayList<>();
            int size = q.size();
            if(flag) {
                while(size-- > 0) {
                    TreeNode node = q.poll();
                    list.add(node.val);
                    if(node.left != null) q.add(node.left);
                    if(node.right != null) q.add(node.right);
                }
            } else {
                while(size-- > 0){
                    TreeNode node = q.pollLast();
                    list.add(node.val);
                    if(node.right != null) q.push(node.right);
                    if(node.left != null) q.push(node.left);
                }
            }
            flag = !flag;
            ans.add(list);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)，n为树的节点数,遍历一次树花费O(n)。
• 空间复杂度：O(n)，队列的空间不超过n,最坏情况树退化为链表为O(n)。