之字形打印二叉树（java 非递归）

梦里梦外; 2022-05-14 10:42 162阅读 0赞

剑指offer算法题

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

public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
    
            if (pRoot == null) {
                return null;
            }
            ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    
            //二叉树的层次标记
            int level = 1;
            //保存二叉树当前层次的结点信息
            Stack<TreeNode> concurrent = new Stack<>();
            concurrent.push(pRoot);
            while (!concurrent.isEmpty()){
                Stack<TreeNode> to = new Stack<>();
                ArrayList<Integer> list = new ArrayList<>();
    
                if (level%2==0){
                    while (!concurrent.isEmpty()){
                        TreeNode node = concurrent.pop();
                        if (node != null) {
                            //将当前的val添加到list中
                            list.add(node.val);
                            //输出当前结点val
                            System.out.print(node.val+" ");
                            //偶数层从有向左记录下层结点
                            if (node.right != null) {
                                to.push(node.right);
                            }
                            if (node.left != null) {
                                to.push(node.left);
                            }
                        }
                    }
                }else {
                    while (!concurrent.isEmpty()){
                        TreeNode node = concurrent.pop();
                        if (node != null) {
                            //将当前的val添加到list中
                            list.add(node.val);
                            //输出当前结点val
                            System.out.print(node.val+" ");
                            //奇数层从左向右记录下一层所有结点
                            if (node.left != null) {
                                to.push(node.left);
                            }
                            if (node.right != null) {
                                to.push(node.right);
                            }
                        }
                    }
                }
                //将一层信息添加到结果列表
                result.add(list);
                //当前层转向下一层
                concurrent = to;
                //层级标记增加
                level++;
                //输出结果换行显示
                System.out.println();
            }
            return result;
        }