For example:
Given binary tree
Given binary tree
{3,9,20,#,#,15,7}
,3 / \ 9 20 / \ 15 7
return its level order traversal as:
用一个queue进行BFS。第二个只需把25行改成add(0, level)[ [3], [9,20], [15,7] ]
public class Solution { //Time: O(n) Space: O(n) public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if (root == null) { return res; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); ArrayList<Integer> level = new ArrayList<Integer>(); for (int i = 0; i < size; i++) { TreeNode cur = queue.poll(); level.add(cur.val); if (cur.left != null) { queue.offer(cur.left); } if (cur.right != null) { queue.offer(cur.right); } } res.add(level); } return res; } }
No comments:
Post a Comment