思路
广度优先遍历的变形。 维护一个 Queue，首先将根节点加入到 Queue 中。 维护两个计数器，numsOfThisLevel：记录本层的节点数， numsOfSonLevel：记录下一层的节点数。 维护一个外层 List<List>，和一个 内层的 List。 循环，当 Queue 不为空时：
取出一个节点，把它的 val 加入内层List。当它的左节点不为空时，将它的左节点加入到队列中。并且下层的节点数 + 1；当它的右节点不为空时，将它的右节点加入到队列中。并且下层的节点数 + 1；判断内层 List 的大小是否已经等于了本层节点数。如果等于，那么就把 内层 List加入到外层 List 中，然后新建一个内层 List。 并且将两层的计数器，都下移一层（numsOfThisLevel = numsOfSonLevel; numsOfSonLevel = 0）。
最后翻转外层 List。
复杂度分析
假设树有 n 个节点。
时间复杂度O(n)，遍历整棵树。空间复杂度O(n)，空间复杂度取决二叉树的节点数。
代码
public List
<List
<Integer>> levelOrderBottom(TreeNode root
) {
List
<List
<Integer>> ans
= new ArrayList<>();
if (root
== null
){
return ans
;
}
Queue
<TreeNode> treeNodesQueue
= new LinkedList<>();
List
<Integer> nums
= new ArrayList<>();
int numsOfThisLevel
= 1;
int numsOfSonLevel
= 0;
treeNodesQueue
.offer(root
);
while (!treeNodesQueue
.isEmpty()){
TreeNode node
= treeNodesQueue
.poll();
nums
.add(node
.val
);
if (node
.left
!= null
){
treeNodesQueue
.offer(node
.left
);
numsOfSonLevel
++;
}
if(node
.right
!= null
){
treeNodesQueue
.offer(node
.right
);
numsOfSonLevel
++;
}
if (nums
.size() == numsOfThisLevel
){
ans
.add(nums
);
nums
= new ArrayList<>();
numsOfThisLevel
= numsOfSonLevel
;
numsOfSonLevel
= 0;
}
}
Collections
.reverse(ans
);
return ans
;
