《剑指offer》之从上到下打印二叉树Ⅰ、Ⅱ、Ⅲ
1 从上到下打印二叉树Ⅰ
1.1 题目
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
1.2 思路
1.3 题解
二叉树类（下同）：
/** * @desc: 二叉树类 * @author: YanMingXin * @create: 2021/9/13-15:52 **/ public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
算法代码：
/** * @desc: 剑指 Offer 32 - I. 从上到下打印二叉树 * @author: YanMingXin * @create: 2021/9/13-14:28 **/ public class Test01 { /** * 声明队列 */ private Queue<TreeNode> queue = new LinkedList<>(); /** * 声明有序列表 */ private ArrayList<Integer> list = new ArrayList<>(); /** * BFS解决 * * @param root * @return */ public int[] levelOrder(TreeNode root) { //判断临界值 if (root == null) { return new int[0]; } //将root放在队首 queue.add(root); //进行循环 while (!queue.isEmpty()) { //弹出队首元素放在List中 TreeNode node = queue.poll(); list.add(node.val); //广度优先搜索 if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } //将List换成数组 int[] res = new int[list.size()]; for (int i = 0; i < list.size(); i++) { res[i] = list.get(i); } return res; } }
2 从上到下打印二叉树Ⅱ
2.1 题目
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
2.2 思路
2.3 题解
/** * @desc: 剑指 Offer 32 - II. 从上到下打印二叉树 II * @author: YanMingXin * @create: 2021/9/13-14:52 **/ public class Test02 { /** * 声明嵌套链表 */ private ArrayList<List<Integer>> list = new ArrayList<>(); /** * 声明队列 */ private Queue<TreeNode> queue = new LinkedList<>(); /** * BFS * * @param root * @return */ public List<List<Integer>> levelOrder(TreeNode root) { //临界条件 if (root != null) { queue.add(root); } while (!queue.isEmpty()) { List<Integer> tmp = new ArrayList<>(); //将队列中的元素全部弹出 for (int i = queue.size(); i > 0; i--) { TreeNode node = queue.poll(); //list添加队列中弹出的元素 tmp.add(node.val); //向队列添加新的元素，留作下次循环使用 if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } list.add(tmp); } return list; } }
3 从上到下打印二叉树Ⅲ
3.1 题目
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
3.2 思路
何为双端队列？
双端队列顾名思义就是既可以在队首插入也可以在队尾弹出的队列。
因此如果想要达到题目的要求，就可以先判断是奇数还是偶数，并进行队首插入或队尾插入。
3.3 题解
/** * @desc: 剑指 Offer 32 - III. 从上到下打印二叉树 III * @author: YanMingXin * @create: 2021/9/13-15:08 **/ public class Test03 { /** * 声明双端队列 */ private Queue<TreeNode> queue = new LinkedList<>(); /** * 嵌套List */ private List<List<Integer>> res = new ArrayList<>(); /** * BFS+双端队列 * * @param root * @return */ public List<List<Integer>> levelOrder(TreeNode root) { if (root != null) { queue.add(root); } while (!queue.isEmpty()) { LinkedList<Integer> tmp = new LinkedList<>(); for (int i = queue.size(); i > 0; i--) { TreeNode node = queue.poll(); if (res.size() % 2 == 0) { // 偶数层 -> 队列头部 tmp.addLast(node.val); } else { // 奇数层 -> 队列尾部 tmp.addFirst(node.val); } if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } res.add(tmp); } return res; } }
~
