剑指 Offer 32 - I. 从上到下打印二叉树
题目描述
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
思路
层序遍历,遍历出队队列中的节点,其左右节点不为空就进行入队
实现代码
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int[] levelOrder(TreeNode root) { if(root == null){ return new int[0]; } List<Integer> list = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ TreeNode curr = queue.poll(); list.add(curr.val); if(curr.left != null){ queue.offer(curr.left); } if(curr.right != null){ queue.offer(curr.right); } } int[] res = new int[list.size()]; int index = 0; for(int val : list){ //输出到结果数组 res[index++] = val; } return res; } }
剑指 Offer 32 - II. 从上到下打印二叉树 II
题目描述
从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。
思路
层序遍历,先确定当前层级的节点数,再循环出队,左右节点不为空就将其入队
实现代码
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if(root == null){ return res; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); //当前层级的节点数 List<Integer> list = new ArrayList<Integer>(); //将当前层级的节点遍历出队,其左右节点不为空就入队 for(int i = 0; i < size; i++){ TreeNode curr = queue.poll(); list.add(curr.val); if(curr.left != null){ queue.offer(curr.left); } if(curr.right != null){ queue.offer(curr.right); } } res.add(list); } return res; } }
剑指 Offer 32 - III. 从上到下打印二叉树 III
题目描述
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
题目链接:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
正常的层序遍历是按从左到右的顺序打印,而要实现从右到左的顺序打印,若无法改变遍历的顺序,那么不妨对插入集合的顺序进行处理,根据层级决定使用尾插法还是头插法
题目链接:https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
思路
实现代码
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if(root == null){ return res; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int k = 1; //层级 while(!queue.isEmpty()){ int size = queue.size(); //当前层级的节点数 List<Integer> list = new ArrayList<Integer>(); //将当前层级的节点遍历出队,其左右节点不为空就入队 for(int i = 0; i < size; i++){ TreeNode curr = queue.poll(); if(k % 2 != 0){ //奇数层就进行尾插入 list.add(curr.val); }else{ //偶数层就进行头插入,实现从右到左的顺序打印 list.add(0, curr.val); } if(curr.left != null){ queue.offer(curr.left); } if(curr.right != null){ queue.offer(curr.right); } } k++; res.add(list); } return res; } }