JZ76 删除链表中重复的结点

题目

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如，给定的二叉树是{1,2,3,#,#,4,5}
该二叉树之字形层序遍历的结果是
[
[1],
[3,2],
[4,5]
]

方法 非递归层次遍历

思路

算法实现

按照层次遍历按层打印二叉树的方式，每层分开打印，然后对于每一层利用flag标记，
第一层为false，之后每到一层取反一次，如果该层的flag为true，则记录的数组整个反转即可。

具体做法：
    step 1：首先判断二叉树是否为空，空树没有打印结果。
    step 2：建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面，初始化flag变量。
    step 3：每次进入一层，统计队列中元素的个数，更改flag变量的值。因为每当访问完一层，
            下一层作为这一层的子节点，一定都加入队列，而再下一层还没有加入，因此此时队列中的元素个数就是这一层的元素个数。
    step 4：每次遍历这一层这么多的节点数，将其依次从队列中弹出，然后加入这一行的一维数组中，如果它们有子节点，依次加入队列排队等待访问。
    step 5：访问完这一层的元素后，根据flag变量决定将这个一维数组直接加入二维数组中还是反转后再加入，然后再访问下一层。

代码

package mid.JZ77按之字形顺序打印二叉树;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        TreeNode head = pRoot;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        //如果为空，直接返回
        if (head == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(head);
        //记录是否反转
        boolean flag = true;
        while (!queue.isEmpty()) {
            ArrayList<Integer> row = new ArrayList<>();
            int n = queue.size();
            flag = !flag;
            for (int i = 0; i < n; i++) {
                TreeNode p = queue.poll();
                row.add(p.val);
                if (p.left != null) {
                    queue.offer(p.left);
                }
                if (p.right != null) {
                    queue.offer(p.right);
                }
            }
            //奇数行反转，偶数行不反转
            if (flag) {
                Collections.reverse(row);
            }
            res.add(row);
        }
        return res;
    }
}