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,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ] Straight forward solution: root node in => left and right children out . -- Lv1 lv 1 nodes in => lv 2 nodes out...... until no more next lv.
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
/**
* @param TreeNode $root
* @return Integer[][]
*/
function levelOrder($root) {
$q = [];
$result = [];
if($root === null){
return $result;
}
$q[] = $root;
while (count($q) > 0){
$current_level = [];
$current_result = [];
foreach ($q as $node){
if ($node->left !== null)
$current_level[] = $node->left;
$current_result[] = $node->val;
if ($node->right !== null)
$current_level[] = $node->right;
}
$q = $current_level;
$result [] = $current_result;
}
return $result;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> r = new ArrayList<>();
if(root == null){
return r;
}
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
int sizeSnapshot = q.size();
List<Integer> current_level = new ArrayList<>();
for(int i = 0; i < sizeSnapshot; i ++){
TreeNode t = q.poll();
if(t.left != null){
q.add(t.left);
}
current_level.add(t.val);
if(t.right != null){
q.add(t.right);
}
}
r.add(current_level);
}
return r;
}
}