二叉树的层序遍历:
LeetCode102 给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
思路:
如果我们用树形结构去实现层序遍历,3连接9,20;20连接15,7
我们没有办法去按顺序的记录每一层的元素,因为连接的规律造成,我们需要记录是第几层, 和每一层对应的值。
如果用队列去实现会更加方便。
我们按中左右顺序不断将元素加入队列中,我们只需要控制队列的出队列个数,即使跨层也没有关系,每一层的出队列个数固定。
// 102.二叉树的层序遍历 class Solution { public List<List<Integer>> resList = new ArrayList<List<Integer>>(); public List<List<Integer>> levelOrder(TreeNode root) { //checkFun01(root,0); checkFun02(root); return resList; } //DFS--递归方式 public void checkFun01(TreeNode node, Integer deep) { if (node == null) return; deep++; if (resList.size() < deep) { //当层级增加时,list的Item也增加,利用list的索引值进行层级界定 List<Integer> item = new ArrayList<Integer>(); resList.add(item); } resList.get(deep - 1).add(node.val); checkFun01(node.left, deep); checkFun01(node.right, deep); } //BFS--迭代方式--借助队列 public void checkFun02(TreeNode node) { if (node == null) return; Queue<TreeNode> que = new LinkedList<TreeNode>(); que.offer(node); while (!que.isEmpty()) { List<Integer> itemList = new ArrayList<Integer>(); int len = que.size(); while (len > 0) { TreeNode tmpNode = que.poll(); itemList.add(tmpNode.val); if (tmpNode.left != null) que.offer(tmpNode.left); if (tmpNode.right != null) que.offer(tmpNode.right); len--; } resList.add(itemList); } } }
LeetCode 107.二叉树的层次遍历II
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
思路:
相当于对之前的二叉树顺序层次遍历进行一个reverse操作即可。
// 107. 二叉树的层序遍历 II public class N0107 { /** * 解法:队列,迭代。 * 层序遍历,再翻转数组即可。 */ public List<List<Integer>> solution1(TreeNode root) { List<List<Integer>> list = new ArrayList<>(); Deque<TreeNode> que = new LinkedList<>(); if (root == null) { return list; } que.offerLast(root); while (!que.isEmpty()) { List<Integer> levelList = new ArrayList<>(); int levelSize = que.size(); for (int i = 0; i < levelSize; i++) { TreeNode peek = que.peekFirst(); levelList.add(que.pollFirst().val); if (peek.left != null) { que.offerLast(peek.left); } if (peek.right != null) { que.offerLast(peek.right); } } list.add(levelList); } List<List<Integer>> result = new ArrayList<>(); for (int i = list.size() - 1; i >= 0; i-- ) { result.add(list.get(i)); } return result; } }
原文地址:http://www.cnblogs.com/dwj-ngu/p/16856304.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性