【二叉树】剑指offer 77 按之字形顺序打印二叉树

描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

输出

[[1],[3,2],[4,5]]

栈解法

用两个栈来存奇数层和偶数层的节点，如果当前为奇数层则先入栈左孩子再入栈右孩子，如果为偶数层则先入栈右孩子再入栈左孩子

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

public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot == null)
            return res;
        boolean toright = true; // 向右输出
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.add(pRoot);

        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            ArrayList<Integer> tmp = new ArrayList<>();
            if (toright) {
            	// 向右输出 奇数层
                while (!stack1.isEmpty()) {
                    TreeNode top = stack1.pop();
                    tmp.add(top.val);
                    if (top.left != null)
                        stack2.add(top.left);
                    if (top.right != null)
                        stack2.add(top.right);
                }
                toright = false;

            } else {
            	// 向右输出 偶数层
                while (!stack2.isEmpty()) {
                    TreeNode top = stack2.pop();
                    tmp.add(top.val);
                    if (top.right != null)
                        stack1.add(top.right);
                    if (top.left != null)
                        stack1.add(top.left);
                }
                toright = true;
            }
            res.add(tmp);
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode r = new TreeNode(8);
        r.left = new TreeNode(6);
        r.right = new TreeNode(10);
        r.left.left = new TreeNode(5);
        r.left.right = new TreeNode(7);
        r.right.left = new TreeNode(9);
        r.right.right = new TreeNode(11);
        System.out.println(new Solution().Print(r));
    }
}