LeetCode.107. 二叉树的层序遍历 II
BFS
这道题与102层序遍历几乎一致,唯一不同的就是输出的ansList,本题是从底层到上层的,代码中的区别为,在将每层的遍历结果levelList加入ansList时,自顶向下的层序遍历时每次添加在尾部,而本题的方法时添加在头部;
class Solution { public List> levelOrderBottom(TreeNode root) { // 利用链表来实现在链表头添加元素,实现自底向上的层序遍历 List
> ansList = new linkedList<>(); Queue
queue = new linkedList<>(); if (root == null) { return ansList; } queue.offer(root); while (!queue.isEmpty()) { List levelList = new ArrayList<>(); int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode tmpNode = queue.poll(); levelList.add(tmpNode.val); if (tmpNode.left != null) { queue.offer(tmpNode.left); } if (tmpNode.right != null) { queue.offer(tmpNode.right); } } // 在链表位置0加入levelList ansList.add(0, levelList); } return ansList; } }
复杂度分析:
时间复杂度:O(n)空间复杂度:O(n)
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)