首页 > 代码库 > 【LeetCode】102. Binary Tree Level Order Traversal-二叉树水平顺序遍历
【LeetCode】102. Binary Tree Level Order Traversal-二叉树水平顺序遍历
一、描述:
二、思路:
二叉树或一般树的水平层次遍历,可以使用BFS(广度搜素)算法,使用队列Queue标记每一层的结点元素;
Queue:先进先出, 后进后出。可以保证每一层遍历时的结点顺序;
BFS:类似于电影中的病毒传染,先感染靠近自己的,再由易感染层感染更外层…(我理解的就是这么个理);
该题二叉树中,先把根结点压入队列,当队列不为空时,移除队首结点,并判断该结点的左右子树中有无非空结点,若存在,则再次入队对应的左右子树结点……同一层的每个结点循环以上操作,直至队列为空,循环结束。
三、代码:
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 List<List<Integer>> list1 = new ArrayList<List<Integer>>(); 12 Queue<TreeNode> queue =new LinkedList<TreeNode>(); 13 14 public List <List<Integer>> levelOrder(TreeNode root) { 15 if(root==null){ 16 return list1; 17 } 18 queue.offer(root); 19 while(!queue.isEmpty()){ 20 List<Integer> list2 = new ArrayList<Integer>(); 21 int size = queue.size(); 22 for(int i=0;i<size;i++){ 23 TreeNode node = queue.remove(); 24 list2.add(node.val); 25 if(node.left!=null){ 26 queue.offer(node.left); 27 } 28 if(node.right!=null){ 29 queue.offer(node.right); 30 } 31 } 32 list1.add(list2); 33 } 34 return list1; 35 } 36 }
【LeetCode】102. Binary Tree Level Order Traversal-二叉树水平顺序遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。