102. Binary Tree Level Order Traversal.md

107. Binary Tree Level Order Traversal II

Problem

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,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

tag:

• tree
• bfs

Solution

类似于Binary Tree Level Order Traversal I 对二叉树宽度优先搜索，并记录每层的节点数，遍历完一层后，把结果插入到链表头部，再进行下一层遍历

java

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        if (root==null) return res;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while(!q.isEmpty()) {
            int levelNum = q.size();
            List<Integer> subList = new LinkedList<Integer>();
            for(int i=0; i<levelNum; i++) {
                if(q.peek().left!=null) q.offer(q.peek().left);
                if(q.peek().right!=null) q.offer(q.peek().right);
                subList.add(q.poll().val);
            }
            res.add(0, subList);
        }
        return res;
    }

go