北京城市建设档案馆网站,wordpress主题太臃肿,网站服务器出问题,应届毕业生招聘官网Problem: 107. 二叉树的层序遍历 II 文章目录 思路解题方法复杂度Code同类型补充题#xff1a; 思路 BFS的核心是借助队列#xff0c;将树的每一层节点先添加到其中#xff0c;再在处理当前层时#xff08;将当前层的节点出队列#xff09;同时将下一层的节点添加到队列中… Problem: 107. 二叉树的层序遍历 II 文章目录 思路解题方法复杂度Code同类型补充题 思路 BFS的核心是借助队列将树的每一层节点先添加到其中再在处理当前层时将当前层的节点出队列同时将下一层的节点添加到队列中最终若队列为空时表示树已经遍历完了 解题方法 1.先将root节点放入队列中在此操作之前先判断树是否为空 2.记录当前队列中的节点个数表示处理当前层的节点个数有多少 3.依次取出当前队列中的节点并将其值添加到集合中同时判断当前层的下一层节点是否存在若存在再将其添加到队列中。循环往复直到队列为空 复杂度
时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( n ) O(n) O(n) Code /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {//Time Complexity: O(lonN)//Space Complexity: O(n)public ListListInteger levelOrderBottom(TreeNode root) {if (root null) return new ArrayListListInteger();//最终结果集合ListListInteger res new ArrayListListInteger();//存取每层节点的队列QueueTreeNode tmp new LinkedList();//将root节点添加到队列中tmp.add(root);while (!tmp.isEmpty()) {ListInteger level new ArrayList();int curLevelSize tmp.size();for (int i 0; i curLevelSize; i) {//先将当前层的节点取出TreeNode curLevelNode tmp.poll();//添加到当前层的集合level.add(curLevelNode.val);//将当前层的孩子节点添加到队列if (curLevelNode.left ! null) {tmp.add(curLevelNode.left);}if (curLevelNode.right ! null) {tmp.add(curLevelNode.right);}}//将当前层集合添加到最终结果集res.add(level);}//将最终结果集翻转Collections.reverse(res);return res;}
}同类型补充题 Problem: 102. 二叉树的层序遍历 Problem: 107. 二叉树的层序遍历 II
