问题描述
看题点链接：https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new LinkedList<List<Integer>>();
//corner case
if(root == null) return res;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
//to counter numbers of element in this level in order to decide how many time it should pop
int size = queue.size();
//to save elements in every level
List<Integer> list = new LinkedList<>();
for(int i = 0; i < size; i++){
TreeNode node = queue.pop();
list.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
res.add(list);
}
Collections.reverse(res);
return res;
}
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)
