剑指Offer——将二叉树按之字形打印

题目描述

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

二叉树样例

（图片来自百度百科）

按之字形打印：

F
E C
A D H G
M B

解题思路

还是基于层次遍历进行改装。如果根节点算第一层的话，那么就是奇数层从左到右，偶数层从右到左。详细的描述可以参考剑指Offer。

《剑指》里面c++语言直接定义了：

std::stack<BinaryTreeNode*> levels[2];

相当于直接定义了一个数组，数组的基础元素是栈。我按照相同的方法Java中使用，表示并不可以。

Stack<TreeNode>[] stacks = new Stack[2];
stacks[current].push(pRoot);
// 定义时候可以，但是push时候 直接会报错：
/*
Exception in thread "main" java.lang.NullPointerException
    at PrintBTZigzag.Print(PrintBTZigzag.java:23)
    at PrintBTZigzag.main(PrintBTZigzag.java:53)
ERROR: JDWP Unable to get JNI 1.2 environment, jvm->GetEnv() return code = -2
JDWP exit error AGENT_ERROR_NO_JNI_ENV(183):  [util.c:840]
*/

题解

方案一：使用队列。这里的关键trick是 ArrayList 可以头插入或者尾插入（奇数层尾插入，偶数层头插入）。

    // 队列形式  技巧有两点：
    //  1. queue.size 实际上获取的是一层的结点。
    //  2. 加入ArrayList时，选择头加入 或 尾加入
public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if(pRoot == null) return  result;
        // 双端队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        int row = 1;
        ArrayList<Integer> temp ;
        while(!queue.isEmpty()){
            // trick1 这个时候回去的队列的长度，实际就是当前层的所有节点数。
            int size = queue.size();
            temp = new ArrayList<>();
            // 当前层遍历一遍
            for (int i = 0; i < size; i++) {
                // 去掉第一个元素
                TreeNode p = queue.poll();
                if (p.left!= null)
                    queue.offer(p.left);
                if (p.right!=null)
                    queue.offer(p.right);
                // trick 2
                if (row%2==0){
                    // 偶数层 头插入
                    temp.add(0,p.val);
                }
                else {
                    // 奇数层 尾插入
                    temp.add(p.val);
                }
            }
            row++;
            result.add(temp);
        }
        return result;
    }

方案二：使用两个栈，一个栈来存奇数层，一个来存偶数层。关键点在：遍历一层结束后，肯定是一个栈空，另一个栈均为下一层结点。

// 双栈的形式
public ArrayList<ArrayList<Integer>> Print2(TreeNode root){
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(root);
    while(!stack1.isEmpty() || !stack2.isEmpty()){
        ArrayList<Integer> temp = new ArrayList<>();
        // stack1 空 那么遍历stack2 结点压入stack1
        if (stack1.isEmpty()){
            while(!stack2.isEmpty()) {
                TreeNode p = stack2.pop();
                temp.add(p.val);
                // 注意压入策略  先右再左
                if (p.right != null) stack1.push(p.right);
                if (p.left != null) stack1.push(p.left);
            }
        }
        // stack2 空 那么遍历stack1 结点压入stack2
        else if (stack2.isEmpty()){
            while(!stack1.isEmpty()) {
                TreeNode p = stack1.pop();
                temp.add(p.val);
                // 注意压入策略 先左再有
                if (p.left != null) stack2.push(p.left);
                if (p.right != null) stack2.push(p.right);
            }
        }
        result.add(temp);
    }
    return result;
}