给定一个二叉树,返回其节点值自底向上的层序遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如:
给定二叉树 [3,9,20,null,null,15,7],
返回其自底向上的层序遍历为:
![YKCS5EH@R0J1QP@}CQFN%M.png
/**
* 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 {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
LinkedList<List<Integer>> res = new LinkedList<>();
if(root == null){
return res;
}
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while(q.size()>0){
int size = q.size();
List<Integer> list = new ArrayList<>();
while(size>0){
TreeNode cur = q.poll();
list.add(cur.val);
if( cur.left != null){
q.add(cur.left);
}
if(cur.right!= null){
q.add(cur.right);
}
size--;
}
res.addFirst(list);
}
return res;
}
}
notes:实际就是层序遍历,用linkedList.addFirst() api每次层序遍历的往头结点插就可以了