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

题目描述:

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

解题思路:

//1.使用两个栈来分别存储奇数层节点和偶数层节点。
//2.注意两个栈的插入顺序是不同的。
//3.对于奇数层来说，也就是从左往右的顺序，先添加左子树，然后添加右子树。对于偶数层，刚好相反，先添加右子树，然后添加左子树。

import java.util.ArrayList;
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;
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(pRoot);
        int level = 1;
        while (!s1.empty()||!s2.empty()) {
            if (level %2 != 0) {
                ArrayList<Integer> list = new ArrayList<>();
                while (!s1.empty()) {
                    TreeNode node = s1.pop();
                    if (node!= null) {
                        list.add(node.val);
                        s2.push(node.left);//因为偶数层，先右后左，所以要先放左子树，栈
                        s2.push(node.right);
                        
                    }
                }
                  if (!list.isEmpty()) {
                        res.add(list);
                        level++;
                    }
            }
            else {
                ArrayList<Integer> list = new ArrayList<>();
                while (!s2.empty()) {
                    TreeNode node = s2.pop();
                    if (node!= null) {
                        list.add(node.val);
                        s1.push(node.right);
                        s1.push(node.left);
                        
                    }
                }
                  if (!list.isEmpty()) {
                        res.add(list);
                        level++;
                    }
            }
        }
        return res;
    }
 
}