题目描述

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

解题思路

1，用两个栈来实现，stack1存放奇数行的，stack2存放偶数行的
2，stack1先push右子节点后push左子节点，stack2反之
3，交替打印和push

代码实现

package 二叉树;

import java.util.ArrayList;
import java.util.Stack;

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

    public ArrayList<ArrayList<Integer>> IntPrint(TreeNode pRoot) {

    Stack<TreeNode> stack1 = new Stack<TreeNode>();// 存放奇数层的所有元素
    Stack<TreeNode> stack2 = new Stack<TreeNode>();// 存放偶数层的所有元素
    ArrayList<ArrayList<Integer>> listall = new ArrayList<ArrayList<Integer>>(); // 总的集合元素
        stack1.push(pRoot);
        int level = 1; // 从第一层开始
        while (!stack1.isEmpty() || !stack2.isEmpty()) {  //这里是易错点条件一定要加！
            if (level % 2 != 0) { // 如果当前层是奇数层
                ArrayList<Integer> list = new ArrayList<Integer>();
                while (!stack1.isEmpty()) {
                    TreeNode current = stack1.pop();
                    if (current != null) {
                        list.add(current.val);
                        //System.out.print(current.val + " ");
                        if (current.left != null) { //偶数层是先放左节点
                            stack2.push(current.left);
                        }
                        if (current.right != null) {
                            stack2.push(current.right);
                        }
                    }
                }
                if (!list.isEmpty()) {
                    listall.add(list);
                    level++;   //变为偶数层
                    System.out.println();
                }
            } else {
                ArrayList<Integer> list = new ArrayList<Integer>();
                while (!stack2.isEmpty()) {
                    TreeNode current = stack2.pop();
                    if (current != null) {
                        list.add(current.val);
                        System.out.print(current.val + " ");

                        if (current.right != null) {           //奇数层是先放右节点
                            stack1.push(current.right);
                        }
                        if (current.left != null) {
                            stack1.push(current.left);
                        }
                    }
                }
                if (!list.isEmpty()) {
                    listall.add(list);
                    level++;
                    System.out.println();
                }
            }

        }
        return listall;
    }

    public static void main(String[] args) {

    }

}

易错点

当两个栈都为空的时候应该跳出循环不再加入listall