[剑指Offer] 按之字形顺序打印二叉树

题目链接

https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=13&tqId=11212&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

题解

法一：用两个栈分别存奇数层和偶数层，很好的利用栈的特性实现之字形遍历。

todo

法二：还可以利用双向链表实现。

代码(法一：两个栈实现)

import java.util.ArrayList;
import java.util.Stack;
/*
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) {
        int layer=1;
        Stack<TreeNode> sOdd=new Stack<>();
        Stack<TreeNode> sEven=new Stack<>();
        ArrayList<ArrayList<Integer>> ansList=new ArrayList<ArrayList<Integer>>();
        
        if(pRoot==null) {
            return ansList;
        } 
        sOdd.push(pRoot);
        
        while(!sOdd.isEmpty()||!sEven.isEmpty()) {
            if(layer%2==1) {
                ArrayList<Integer> arrList=new ArrayList<>();
                while(!sOdd.isEmpty()) {
                    TreeNode node=sOdd.pop();
                    if(node!=null) {//
                        arrList.add(node.val);
                        sEven.push(node.left);
                        sEven.push(node.right);
                    }
                }
                if(!arrList.isEmpty()) {
                    ansList.add(arrList);
                    ++layer;
                }
            }
            else {
                ArrayList<Integer> arrList=new ArrayList<>();
                while(!sEven.isEmpty()) {
                    TreeNode node=sEven.pop();
                    if(node!=null) {
                        arrList.add(node.val);
                        sOdd.push(node.right);
                        sOdd.push(node.left);
                    }
                }
                if(!arrList.isEmpty()) {
                    ansList.add(arrList);
                    ++layer;
                }
            }
        }
        return ansList;
    }

}

[剑指Offer] 按之字形顺序打印二叉树

原文：https://www.cnblogs.com/coding-gaga/p/10934441.html