题目描述:请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
自己做了,没做出来,看了别人的实现,自己写了一遍,参考:https://blog.nowcoder.net/n/ce221364d0a644d49277c3623a6b8c26?f=comment
思路:
二叉树层级遍历,分层加入队列;
从队列中取出来节点,把节点值加入子集合,子集合加入总集合;
增加标记位,标记是否需要反转;
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>(); if (pRoot == null) { return arrayLists; } // 创建队列 LinkedList<TreeNode> queue = new LinkedList<>(); boolean reverse = false; queue.add(pRoot); while (!queue.isEmpty()) { // 每一层new一个集合 ArrayList<Integer> list = new ArrayList<>(); int size = queue.size(); for (int i = 0; i < size; i++) { // 队列中循环弹出节点; TreeNode node = queue.poll(); if (node == null) { continue; } // 判断是否需要反转,如果需要,总是将节点值加到list的0位置 if (!reverse) { list.add(node.val); } else { list.add(0, node.val); } // queue中加入下一层级的节点,循环的过程中会把下一层所有节点加到队列 queue.add(node.left); queue.add(node.right); } // 是否取反,标记位取反 reverse = !reverse; if(list.size() != 0){ arrayLists.add(list); } } return arrayLists; }