題目描述

給定一個(gè)二叉樹，返回該二叉樹的之字形層序遍歷，（第一層從左向右，下一層從右向左，一直這樣交替）
數(shù)據(jù)范圍：0≤n≤1500,樹上每個(gè)節(jié)點(diǎn)的val滿足∣val∣<=1500
要求：空間復(fù)雜度：O(n)，時(shí)間復(fù)雜度：O(n)

示例

image.png

輸入：{1,2,3,#,#,4,5}
輸出： [[1],[3,2],[4,5]]
說明：如題面解釋，第一層是根節(jié)點(diǎn)，從左到右打印結(jié)果，第二層從右到左，第三層從左到右。

思路

這其實(shí)就是一個(gè)升級版的層序遍歷.
觀察其特點(diǎn),無非就是奇數(shù)層和偶數(shù)層的輸出順序不一樣. 這樣就有了初步的解題思路,設(shè)置標(biāo)識符flag(可以為整數(shù)型,也可以為boolean類型,整數(shù)類型無非就是對奇偶數(shù)的判斷).
其余的思路就是層序遍歷的思路,在每遍歷新的一層之前,改變flag的值!flag(這里以boolean類型為例),然后就是利用Collections.reverse(list)對鏈表進(jìn)行翻轉(zhuǎn).
詳情可看代碼

這里,小編再提一下我初次遇到這道題的思路,前面的幾乎一樣,就是在實(shí)現(xiàn)鏈表反轉(zhuǎn)這里,小編不熟悉Java庫,沒想到還有Colection.reverse這個(gè)方法可以用.
所以,小編在想反轉(zhuǎn)的時(shí)候首先就想到了咱們的棧,也就是根據(jù)flag的值判斷,從隊(duì)列出來的值是否需要進(jìn)一次棧實(shí)現(xiàn)反轉(zhuǎn)

代碼實(shí)現(xiàn)

import java.util.*;
import java.util.ArrayList;

/*
public 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) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        TreeNode head = pRoot;
        if(head==null){
            return res;
        }
        Queue<TreeNode> temp = new LinkedList<TreeNode>();
        temp.offer(head);
        TreeNode p;
        boolean flag = true;
        while(!temp.isEmpty()){
            ArrayList<Integer> list = new ArrayList<Integer>();
            int size = temp.size();
            flag = !flag;
            for(int i=0;i<size;++i){
                p = temp.poll();
                if(p.left!=null){
                    temp.offer(p.left);
                }
                if(p.right!=null){
                    temp.offer(p.right);
                }
                list.add(p.val);
            }
            if(flag){
                Collections.reverse(list);
            }
            res.add(list);
        }
        return res;
    }
}