107. Binary Tree Level Order Tra

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:

Given binary tree [3,9,20,null,null,15,7],
  3
  / \
9 20
    / \
  15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]

题目

二叉树层序遍历，返回一个list集合，里面装了每一层的list集合，而且是从叶子到根的倒序

思路

首先二叉树层序遍历，利用队列，头结点先入队，以后遍历就从队列里弹，弹出一个将其左右孩子入队，再操作该节点。最后把list集合倒序即可
难点是记录层的开始和结束，这里需要利用两个变量，代码如下：

代码

 public List<List<Integer>> levelOrderBottom(TreeNode root) {
         List<List<Integer>> result =new ArrayList<>();
         List<Integer> listLevel =new ArrayList<>();
         Queue<TreeNode> q = new LinkedList<>();
         if(root==null){
                return result;
            }
         int curLevelNum=1;//当前层节点数
         int nextLevelNum=0;//下一层节点数
         
         TreeNode p ;
         q.offer(root);
         while (q.size()>0) {
            p=q.poll();
            listLevel.add(p.val);//加入一个节点
            curLevelNum--;//当前层节点数-1
            if (p.left!=null) {
                q.offer(p.left);
                nextLevelNum++;//有左孩子下一层+1
            }
            if (p.right!=null) {
                q.offer(p.right);
                nextLevelNum++;//有右孩子下一层+1
            }
            
            if (curLevelNum==0) {
                curLevelNum=nextLevelNum;
                nextLevelNum=0;
                result.add(listLevel);//把该层节点list放进去
                listLevel=new ArrayList<Integer>();//再新建一个
                
            }
            
        }
         reverse(result);
         
        return result;
        }

    private void reverse(List<List<Integer>> result) {
        int n = result.size();
        int start=0;
        int last=n-1;
        while (start<=last) {
            List<Integer> list = result.get(last);
            result.set(last, result.get(start));
            result.set(start, list);
            start++;
            last--;
        }
    }