LeetCode -- Binary Tree Level Order Traversal
题目描述：
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]
]
本题考查基本的BFS算法，把逐层遍历的节点添加到结果集中。
实现代码：
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]
]
本题考查基本的BFS算法，把逐层遍历的节点添加到结果集中。
实现代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public IList<IList<int>> LevelOrder(TreeNode root)
{
if(root == null){
return new List<IList<int>>();
}
var starts = new List<TreeNode>();
if(root.left != null){
starts.Add(root.left);
}
if(root.right != null){
starts.Add(root.right);
}
var result = new List<IList<int>>();
result.Add(new List<int>(){root.val});
Travel(starts, result);
return result;
}
public void Travel(IList<TreeNode> parents, IList<IList<int>> result)
{
// stop
if(parents == null || parents.Count == 0){
return ;
}
// add previous level nodes
result.Add(parents.Select(x=>x.val).ToList());
// get each parent childs and combine, do BFS
var children = new List<TreeNode>();
foreach(var n in parents){
var nodes = Children(n);
//add children
children.AddRange(nodes);
}
Travel(children, result);
}
private IList<TreeNode> Children(TreeNode n)
{
var nodes = new List<TreeNode>();
if(n.left != null){
nodes.Add(n.left);
}
if(n.right != null){
nodes.Add(n.right);
}
return nodes;
}
}