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;
    }
}