劍指Offer-Java】按之字形順序列印二叉樹

按之字形順序列印二叉樹

• 題目描述
• 思路
• 實作

題目描述

請實作一個函數按照之字形列印二叉樹，即第一行按照從左到右的順序列印，第二層按照從右至左的順序列印，第三行按照從左到右的順序列印，其他行以此類推。

思路

設定标志變量flag:奇數層flag=false，偶數層flag=true

用隊列存放每一層結點，每周遊完一層，就将flag取反

周遊完一層，利用flag判斷是否需要将該層結點反序（偶數層需要反序）

實作

import java.util.*;
/*
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>>();
        Queue<TreeNode> q=new LinkedList<>();
        if(pRoot==null) return res;

        //奇數層flag=false，偶數層flag=true
        boolean flag=true;
        //先把根加入隊列
        q.offer(pRoot);
        while(!q.isEmpty()){
            flag=!flag;    //每周遊完一層，就将flag取反（第一次循環，第一層是根，flag為false）
            int size=q.size();  //size記錄隊列大小，即每層結點個數
            ArrayList<Integer> list=new ArrayList<>();    //list存放每一層的結點值
            //周遊每層結點
            for(int i=0;i<size;i++){   //這裡的size不可以直接寫q.size()，必須使程式再回到外層循環判斷，不可隻執行内部for循環
                TreeNode cur=q.remove();
                list.add(cur.val);
                if(cur.left!=null){
                    q.offer(cur.left);
                }
                if(cur.right!=null){
                    q.offer(cur.right);
                }
            }
            //周遊完一層後，根據flag判斷是奇數層還是偶數層，決定是否需要反轉
            if(flag){
                Collections.reverse(list);
            }
            res.add(list);
        }
        return res;
    }
}

           

其他列印二叉樹的文章：

按層列印（不分行）：從上往下列印二叉樹

按層列印（分行）：把二叉樹列印成多行