leetcode:103. 二叉树的锯齿形层次遍历（bfs）

Bertha 。 2021-09-28 11:36 281阅读 0赞

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

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

3
       / \
      9  20
        /  \
       15   7

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

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

package LeetCode;
    
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    public class ZigzagLevelOrder {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            if (root == null) return res;
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode r = root;
            queue.add(r);
            int i = 0;
            while (!queue.isEmpty()) {
                int count = queue.size();
                List<Integer> re = new ArrayList<>();
                while (count > 0) {
                    TreeNode n = queue.poll();
                    re.add(n.val);
                    if (n.left != null) queue.add(n.left);
                    if (n.right != null) queue.add(n.right);
                    count--;
                }
                List<Integer> rs = new ArrayList<>();
                if (i % 2 != 0) {
                    for (int j = re.size() - 1; j >= 0; j--) {
                        rs.add(re.get(j));
                    }
                } else {
                    rs = re;
                }
                res.add(rs);
                i++;
            }
            return res;
        }
    }