剑指offer12

题目描述

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

解题思路分析

如果需要按之字形打印二叉树话，我们其实很快就能想到用两个栈来实现
先将根节点入stack1，然后开始打印过程，当打印的奇数层的时候，将正在被打印的节点左右节点入stack2，这里得捋清楚入栈的时候到底是先入左孩子还是右孩子，从咱们这个题目来看，当再打印stack1中的节点时，由于要求方向输出，所有在将正在打印的节点的左孩子先入栈，然后再入它的右孩子，相反的，如果是在打印stack2中的节点时，应该先将正在打印的节点的右孩子先入栈，然后再入它的左孩子，还有我们需要一个标识来记录我们正在打印的是奇数层还是偶数层，这样分析下来，代码就好写了

代码实现

public ArrayList<ArrayList<Integer>> print(TreeNode pRoot) {
    if(pRoot == null) {
        return null;
    }
    ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
    //声明两个栈来存储节点
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(pRoot);
    int layer = 1;
    while (!stack1.isEmpty() || !stack2.isEmpty()) {
        if ((layer & 1) == 1) {
            ArrayList<Integer> list = new ArrayList<>();
            while (!stack1.isEmpty()) {
                TreeNode node = stack1.pop();
                if (node != null) {
                    s2.push(node.left);
                    s2.push(node.right);
                    list.add(node.val);
                }
            }
            if (!list.isEmpty()) {
                lists.add(list);
                layer++;
            }
        }else {
            ArrayList<Integer> list = new ArrayList<>();
            while (!stack2.isEmpty()) {
                TreeNode node = stack2.pop();
                if (node != null) {
                    s1.push(node.right);
                    s1.push(node.left);
                    list.add(node.val);
                }
            }
            if (!list.isEmpty()) {
                lists.add(list);
                layer++;
            }
        }
    }
    return lists;
}