LEETCODE 103. Binary Tree Zigzag Level Order Traversal 解题思路分析

题目大意：

二叉树的锯齿形层次遍历

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

例如：
给定二叉树 [3,9,20,null,null,15,7],

3
   / \
  9  20
    /  \
   15   7

返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=103

解题思路分析：

之前文章多次讲过，二叉树问题多数情况下应该想到使用dfs或者bfs来解题。本题要求逐行打印，因此bfs相对来说更加适合。

利用bfs广度优先搜索遍历二叉树每一行，如果当前行是偶数行，则正序向返回结果插入数据，反之则逆序插入。bfs的部分完全是模板级别的代码，这里就不在多说了。

实现代码：

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    // 返回结果
    List<List<Integer>> res = new ArrayList<>();
    // root为空，返回res
    if(root==null) return res;
    // bfs用的Queue
    Queue<TreeNode> q = new LinkedList<>();
    // 将root加入Queue
    q.offer(root);
    // 当前行数
    int level=0;
    // 以下为bfs常规代码
    while(q.size()>0){
        int size=q.size();
        // 保存当前行所有节点
        List list = new ArrayList<>();
        // 逐行遍历二叉树
        while(size>0){
            // 取出当前节点
            TreeNode n = q.poll();
            size--;
            // 如果是偶数行，正序插入
            if(level%2==0) list.add(n.val);
            // 奇数行，倒序插入
            else list.add(0, n.val);
            // 左节点不为空，将左节点加入Queue
            if(n.left!=null)q.offer(n.left);
            // 右节点不为空，将右节点加入Queue
            if(n.right!=null)q.offer(n.right);
        }
        // 行数加一
        level++;
        // 将当前行加入返回结果
        res.add(list);
    }
    return res;
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 74.98% of Java online submissions for Binary Tree Zigzag Level Order Traversal.

Memory Usage: 43.3 MB, less than 5.77% of Java online submissions for Binary Tree Zigzag Level Order Traversal.