首页 > 代码库 > Binary Tree Level Order Traversal，层序遍历二叉树，每层作为list，最后返回List<list>
Binary Tree Level Order Traversal，层序遍历二叉树，每层作为list，最后返回List<list>
问题描述：
Given a binary tree, return the level order traversal of its nodes‘ values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3 / 9 20 / 15 7
return its level order traversal as:
[ [3], [9,20], [15,7]]
算法分析：这道题和普通的层序遍历不一样的地方就是，需要每层单独输出。因此可以考虑用来两个队列，每个队列存放不同层的节点。我自己写的代码有重复的结构，并不友好。参考网上，其实将第二个队列赋值给第一个队列就行，就不会有重复代码了。也无需考虑队列空的情况了。
package LeetCode;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Deque;import java.util.List;import java.util.Queue;class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; }}public class BinaryTreeLevelOrderTraversal { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if(root == null) { return res; } Deque<TreeNode> queue1 = new ArrayDeque<>(); Deque<TreeNode> queue2 = new ArrayDeque<>(); queue1.offer(root); while(!queue1.isEmpty() || !queue2.isEmpty()) { List<Integer> list1 = new ArrayList<>(); while(!queue1.isEmpty()) { TreeNode temp = queue1.poll(); if(temp.left != null) { queue2.offer(temp.left); } if(temp.right != null) { queue2.offer(temp.right); } list1.add(temp.val); } if(list1.size() != 0)//队列空的时候，list1的大小为0 res.add(list1); List<Integer> list2 = new ArrayList<>(); while(!queue2.isEmpty()) { TreeNode temp = queue2.poll(); if(temp.left != null) { queue1.offer(temp.left); } if(temp.right != null) { queue1.offer(temp.right); } list2.add(temp.val); } if(list2.size() != 0) res.add(list2); } return res; } public List<List<Integer>> levelOrder2(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); List<Integer> list = new ArrayList<>(); if(root == null) { return res; } ArrayDeque<TreeNode> curr = new ArrayDeque<>(); ArrayDeque<TreeNode> next = new ArrayDeque<>(); curr.offer(root); while(!curr.isEmpty()) { TreeNode temp = curr.poll(); if(temp.left != null) { next.offer(temp.left); } if(temp.right != null) { next.offer(temp.right); } list.add(temp.val); if(curr.isEmpty()) { res.add(list); list = new ArrayList<Integer>(); curr = next; next = new ArrayDeque<>(); } } return res; }}
Binary Tree Level Order Traversal，层序遍历二叉树，每层作为list，最后返回List<list>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。