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

痛定思痛。 2022-09-05 04:24 117阅读 0赞

#### 题目重述 ####

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

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

3
       / \
      9  20
        /  \
       15   7

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

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

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

#### Java实现 ####

class Solution {
        
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        
            List<List<Integer>> result = new ArrayList<>();
            if(root == null){
        
                return result;
            }
            // 标记本轮是从左到右，还是从右到左
            boolean isOrderLeft = true;
            // 空队列，用于层次遍历
            List<TreeNode> q = new ArrayList<>();
            q.add(root);
            while (!q.isEmpty()) {
        
            	// 双端队列，保证从头插入和从尾插入的效率
                Deque<Integer> level = new LinkedList<>();
                int current = q.size();
                // 批次处理，记录size，也就知道某一层都是哪些结点了
                for (int j = 0; j < current; j++) {
        
                    TreeNode t = null;
                    t = q.remove(0);
                    if(isOrderLeft){
        
                        level.addLast(t.val);
                    }else{
        
                        level.addFirst(t.val);
                    }
                    // 队列出队
                    if (t.left != null) {
        
                        q.add(t.left);
                    }
                    if (t.right != null) {
        
                        q.add(t.right);
                    }
                }
                result.add(new LinkedList<>(level));
                isOrderLeft = !isOrderLeft;
            }
            return result;
        }
    }