二叉树遍历（层级、前序、中序、后序）

BinaryTreeTraversal.cs

var root = new TreeNode(1)
{
    Left = new TreeNode(2)
    {
        Left = new TreeNode(4),
        Right = new TreeNode(5)
    },
    Right = new TreeNode(3)
    {
        Left = new TreeNode(6),
        Right = new TreeNode(7)
    }
};

Console.WriteLine("层序遍历 {0}", string.Join(',', LevelOrder(root)));
Console.WriteLine("前序遍历 {0}", string.Join(',', PreOrder(root)));
Console.WriteLine("中序遍历 {0}", string.Join(',', InOrder(root)));
Console.WriteLine("后序遍历 {0}", string.Join(',', PostOrder(root)));

// 前序、中序、后序遍历都属于 [深度优先遍历 depth-first traversal]，它体现了一种 "先走到尽头，再回溯继续" 的遍历方式。
// 深度优先遍历就像是绕着整个二叉树的外围 "走" 一圈，在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后续遍历。
// 时间复杂度 O(n)，空间复杂度 O(n)
// 所谓的前序、中序、后序，就是何时添加根节点，最开始、中间、最后添加根节点

// 前序遍历
List<int> PreOrder(TreeNode? root)
{
    if (root == null)
    {
        return new();
    }

    List<int> list = new();
    // 访问优先级：根节点 -> 左子树 -> 右子树
    list.Add(root.Val);
    list.AddRange(PreOrder(root.Left));
    list.AddRange(PreOrder(root.Right));

    return list;
}

// 中序遍历
List<int> InOrder(TreeNode? root)
{
    if (root == null)
    {
        return new();
    }

    List<int> list = new();
    // 访问优先级：左子树 -> 根节点 > 右子树
    list.AddRange(InOrder(root.Left));
    list.Add(root.Val);
    list.AddRange(InOrder(root.Right));

    return list;
}

// 后序遍历
List<int> PostOrder(TreeNode? root)
{
    if (root == null)
    {
        return new();
    }

    List<int> list = new();
    // 访问优先级：左子树 -> 右子树 -> 根节点
    list.AddRange(PostOrder(root.Left));
    list.AddRange(PostOrder(root.Right));
    list.Add(root.Val);

    return list;
}

/// <summary>
/// [层序遍历 level-order traversal]
/// 从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。
/// 本质上属于 [广度优先遍历 breadth-first traversal]，它体现了一种 “一圈一圈向外扩展” 的逐层遍历方式。
/// 
/// 广度优先遍历通常借助 "队列" 来实现。队列遵循 "先入先出" 的队则，
/// 而广度优先遍历则遵循 "逐层推进" 的规则，两者背后的思想是一致的。
/// 
/// 时间复杂度 O(n)，空间复杂度 O(n)
/// </summary>
List<int> LevelOrder(TreeNode root)
{
    // 初始化队列，加入根节点
    Queue<TreeNode> queue = new();
    queue.Enqueue(root);
    // 初始化一个列表，用于保存遍历序列
    List<int> list = new();
    while (queue.Count > 0)
    {
        TreeNode node = queue.Dequeue(); // 队列出队
        list.Add(node.Val);              // 保存节点值
        if (node.Left != null)
        {
            queue.Enqueue(node.Left);    // 左子节点入队
        }

        if (node.Right != null)
        {
            queue.Enqueue(node.Right);   // 右子节点入队
        }
    }

    return list;
}


// [二叉数 binary tree] 节点
class TreeNode
{
    /// <summary>
    /// 值
    /// </summary>
    public int Val { get; set; }

    /// <summary>
    /// [左子节点 left-child node] 引用
    /// </summary>
    public TreeNode? Left { get; set; }

    /// <summary>
    /// [右子节点 right-child node] 引用
    /// </summary>
    public TreeNode? Right { get; set; }

    public TreeNode(int val) => Val = val;
}