102. 二叉树的层次遍历

题目

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

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

分析

将左右节点与层联系到一起,递归或者队列都可以解决

代码

递归
时间复杂度O(N)
空间复杂度O(N)

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public IList<IList<int>> LevelOrder(TreeNode root)
{
    List<IList<int>> list = new List<IList<int>>();//结果数组
    return root == null ? list : LevelOrder(root, 0, list);//如果null就直接返回 否则开始递归
}
private List<IList<int>> LevelOrder(TreeNode node, int level, List<IList<int>> list)
{
    //当前层没有创建数组
    if (list.Count == level)
    {
        list.Add(new List<int>());
    }
    list[level].Add(node.val);//将当前节点的值添加到对应的层
    if (node.left != null)
    {
        list = LevelOrder(node.left, level + 1, list);
    }
    if (node.right != null)
    {
        list = LevelOrder(node.right, level + 1, list);
    }
    return list;
}

2.迭代
时间复杂度O(N)
空间复杂度O(N)

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public IList<IList<int>> LevelOrder(TreeNode root)
{
    List<IList<int>> list = new List<IList<int>>();//结果数组
    if (root == null)
    {
        return list;
    }
    Queue<KeyValuePair<TreeNode, int>> queue = new Queue<KeyValuePair<TreeNode, int>>();//节点 层,数据对组成的队列
    queue.Enqueue(new KeyValuePair<TreeNode, int>(root, 0));//将根节点加入队列中
    while (queue.Count > 0)
    {
        var kvp = queue.Dequeue();
        if (list.Count == kvp.Value)
        {
            list.Add(new List<int>());
        }
        list[kvp.Value].Add(kvp.Key.val);
        if (kvp.Key.left != null)
        {
            queue.Enqueue(new KeyValuePair<TreeNode, int>(kvp.Key.left, kvp.Value + 1));
        }
        if (kvp.Key.right != null)
        {
            queue.Enqueue(new KeyValuePair<TreeNode, int>(kvp.Key.right, kvp.Value + 1));
        }
    }
    return list;
}