107. Binary Tree Level Order Traversal II.md

102. Binary Tree Level Order Traversal

Problem

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

For example: Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

tag:

• tree
• bfs

Solution

对二叉树宽度优先搜索，并记录每层的节点数，遍历完一层后，纪录结果， 再进行下一层遍历

java

    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        
        if(root==null) return res;
        
        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(subList);
        }
        return res;
    }

go