剑指 Offer 32 - I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [ 3 , 9 , 20 , n u l l , n u l l , 15 , 7 ] [3,9,20,null,null,15,7][3,9,20,null,null,15,7]
3 / \ 9 20 / \ 15 7
返回：
[ 3 , 9 , 20 , 15 , 7 ] [3,9,20,15,7][3,9,20,15,7]
提示：1.节点总数 <= 1000
思考点：善于用Queue队列去实现模拟遍历的顺序，list存储值
public class Solution { public int[] levelOrder(TreeNode root) { if (root == null) { return new int[]{}; } Queue<TreeNode> queue = new ArrayDeque<>(); ArrayList<Integer> list = new ArrayList<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); list.add(node.val); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } int[] arr = new int[list.size()]; for (int i = 0; i < arr.length; i++) { arr[i] = list.get(i); } return arr; } }
剑指 Offer 32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
返回其层次遍历结果：
[ [3], [9,20], [15,7] ]
提示：1.节点总数 <= 1000
思考点：和上一个题一样，不过这里在存储的时候要记得根据每一层的数量来，而每一层的数量就是queue.size()，因此就是多了一个for循环
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new ArrayDeque<>(); if (root == null) { return res; } queue.add(root); while (!queue.isEmpty()) { List<Integer> list = new ArrayList<>(); for (int i = queue.size(); i > 0; i--) { TreeNode node = queue.poll(); list.add(node.val); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } res.add(list); } return res; } }
剑指 Offer 32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
返回其层次遍历结果：
[ [3], [20,9], [15,7] ]
提示： 1. 节点总数 <= 1000
思考点：和上一题不同的是，这里需要按照树节点层次的奇偶性打印。那么奇偶性打印可以根据什么来判断呢？奇偶性可以根据我们要返回的res.size()来看，因为res每存储一层，刚好res.size()的变化和奇偶性的变化是同步的。因此我们可以在上一题的基础上加上一层判断，同时借助双端队列LinkedList来对数据进行插入队尾或者是插入队首
public class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new ArrayDeque<>(); if (root == null) { return res; } queue.add(root); while (!queue.isEmpty()) { LinkedList<Integer> list = new LinkedList<>(); for (int i = queue.size(); i > 0; i--) { TreeNode node = queue.poll(); if ((res.size() & 1) == 0) { list.addLast(node.val); } else { list.addFirst(node.val); } if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } res.add(list); } return res; } }
