我要评论二叉树的层序遍历
层序遍历是广度优先搜索算法（Breadth First Search BFS）的体现，而BFS通常利用队列的先进先出特性来实现。（当然递归方式也能实现）
给定某二叉树如下图所示（图片来源于网络）：
-
利用辅助队列，时间复杂度为O(n)，n为节点数。
BFS初始化：将根节点加入队列（此时队列中就只有根节点一个元素）
BFS循环：当队列为空时跳出循环
1.队首元素出队（队首元素发生改变），并记录该节点值
2.将出队的队首节点的左右子节点依次添加到队列中（若无则跳过）
public int[] levelOrder(TreeNode root) { if(root == null) return new int[0]; //初始化 Queue<TreeNode> queue = new LinkedList<>(){{ add(root); }}; ArrayList<Integer> ans = new ArrayList<>(); //BFS循环 while(!queue.isEmpty()) { TreeNode node = queue.poll(); ans.add(node.val); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } int[] res = new int[ans.size()]; for(int i = 0; i < ans.size(); i++) res[i] = ans.get(i); return res; } -
使用队列先进先出的思想，但不使用辅助队列，而是用指针来实现。这种方式在时间复杂度上与第一种没什么区别，时间复杂度也为O(n)，n为节点数。，不过在空间复杂度上会节省一些。
初始化：将根节点加入到集合中，并初始化指针i。
BFS循环：当指针越过集合的最后一个元素时跳出
1. 将指针所指的“队首”元素的左右子节点依次加入队列（若有）
2.指针i往后移一位，然后循环
class Solution { public int[] levelOrder(TreeNode root) { if (root==null) return new int[0]; //初始化 List<TreeNode> list=new ArrayList<>(); int i=0; list.add(root); //BFS循环 while (i<list.size()){ TreeNode mid=list.get(i); if (mid.left!=null) list.add(mid.left); if (mid.right!=null) list.add(mid.right); i++; } int [] res=new int[list.size()]; for (int j=0;j<list.size();j++) res[j]=list.get(j).val; return res; } } 本文地址：https://blog.csdn.net/qq_39435967/article/details/108033279
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论