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] ]
confused what "{1,#,2,3}"
means?
OJ’s Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:
1 / \ 2 3 / 4 \ 5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}"
.
// BFS 模板方法
public class Solution { public List<List> levelOrder(TreeNode root) { List<List> res = new ArrayList<>(); Queue queue = new LinkedList(); if(root == null){ return res; } queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); ArrayList tempRes = new ArrayList(); for(int i = 0; i < size; i++){ TreeNode curNode = queue.poll(); if(curNode.left != null){ queue.offer(curNode.left); } if(curNode.right != null){ queue.offer(curNode.right); } tempRes.add(curNode.val); } res.add(new ArrayList(tempRes)); } return res; } }