按之字形顺序打印二叉树

用户11162265

发布于 2024-09-25 09:27:48

480

发布于 2024-09-25 09:27:48

文章被收录于专栏：C语言

题目链接：[编程题]按之字形顺序打印二叉树

题目简单描述：

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

思路：

层序遍历该二叉树，将每一层的节点放进一个ArrayList中，同时还要反转第二层、第四层等的ArrayList，这里需用到Collections工具类的reverse()来反转集合。

每一层的处理：把根节点放入队列中。队列不为空时循环。记录当前层的节点数，取出一个节点到该层的列表中，如果该节点有左子节点就添加进队列，如果该节点有右子节点也添加进队列。

代码：

public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        // write code here
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if (pRoot == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        boolean flag = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> list = new ArrayList<>();
            while (size != 0) {
                TreeNode temp = queue.poll();
                list.add(temp.val);
                size--;
                if (temp.left != null) {
                    queue.offer(temp.left);
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                }
            }
            if (flag == true) {
                flag = false;
            } else {
                flag = true;
                Collections.reverse(list);
            }
            ret.add(list);
        }
        return ret;
    }

运行结果：