三种递归遍历顺序只差一行代码；迭代写法为什么一紧张就写不出来；层序遍历靠的不是技巧，而是一个局部变量。
树是 C# 没有替你准备的另一种结构。BCL 里没有 BinaryTreeNode<T>，所以这里的每个程序都自己声明一个：
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}这一篇只讲遍历：怎样按有用的顺序走到每个节点。走到之后要算什么，是第 13 篇的内容。
下面每个程序都是完整的，都在 .NET 10 上跑过，输出直接从运行结果里复制。
模式 56 — 三种递归顺序
前序、中序和后序是同一个函数写了三遍。唯一的区别是访问节点的那一行放在哪里。
三个函数一模一样，只有访问节点的那一行放在哪不同。区别全在这一行：它决定一个节点是在子节点的答案出来之前处理，还是之后处理。
// 1
// / \
// 2 3
// / \ /
// 4 5 6
TreeNode tree = new(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5)),
new TreeNode(3, new TreeNode(6)));
// The three orders differ by ONE line: where the visit sits relative to the
// two recursive calls.
static void PreOrder(TreeNode? n, List<int> outp)
{
if (n is null) return;
outp.Add(n.Value); // visit, then children
PreOrder(n.Left, outp);
PreOrder(n.Right, outp);
}
static void InOrder(TreeNode? n, List<int> outp)
{
if (n is null) return;
InOrder(n.Left, outp);
outp.Add(n.Value); // left, visit, right
InOrder(n.Right, outp);
}
static void PostOrder(TreeNode? n, List<int> outp)
{
if (n is null) return;
PostOrder(n.Left, outp);
PostOrder(n.Right, outp);
outp.Add(n.Value); // children, then visit
}
foreach ((string name, Action<TreeNode?, List<int>> walk) in new (string, Action<TreeNode?, List<int>>)[]
{ ("pre-order ", PreOrder), ("in-order ", InOrder), ("post-order", PostOrder) })
{
List<int> got = [];
walk(tree, got);
Console.WriteLine($"{name} {string.Join(" ", got)}");
}
Console.WriteLine();
Console.WriteLine("pre-order visits a node BEFORE its subtrees -> copying a tree, serialising");
Console.WriteLine("in-order visits left, node, right -> a BST comes out sorted");
Console.WriteLine("post-order visits a node AFTER its subtrees -> freeing, or any answer that");
Console.WriteLine(" depends on both children");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}输出：
pre-order 1 2 4 5 3 6
in-order 4 2 5 1 6 3
post-order 4 5 2 6 3 1
pre-order visits a node BEFORE its subtrees -> copying a tree, serialising
in-order visits left, node, right -> a BST comes out sorted
post-order visits a node AFTER its subtrees -> freeing, or any answer that
depends on both children按位置给它们起名，是通常的教法，但这不是它们有用的原因。真正有用的区别是：处理一个节点时，它的子节点的答案出来了没有。
- 前序处理节点时，对它的子树一无所知。适合复制一棵树、序列化，或者任何只靠节点自身数据就够的场景。
- 中序遍历二叉搜索树，输出是有序的。这不是巧合：这就是二叉搜索树（BST）的定义，只不过换成了遍历的写法。
- 后序等两个子节点都处理完才处理当前节点。凡是要把下面的结果合起来的答案，都是后序，不管你叫不叫它后序。第 13 篇全部是后序。
代价： O(n) 时间，调用栈占 O(h) 空间，h 是树高。
适用场景： 永远。后面所有关于树的内容，都用这套词汇来写。
模式 57 — 不用递归的中序遍历
第 7 篇讲过：C# 遇到栈溢出会直接终止进程，而且捕获不了；而退化的树很深。所以在 C# 里，迭代写法比在其他一些语言里更重要。
很多人一紧张就写不出这个版本，原因是他们想去背代码。其实只要说清楚栈里放的是什么，代码自然就出来了。
手写栈之所以难，是因为说不清栈里放的是什么。一旦把“左边已完成、自己未访问”当作不变式，循环就自己写出来了。而且在退化的树上，它不会像递归版那样栈溢出。
// 4
// / \
// 2 6
// / \ /
// 1 3 5
TreeNode tree = new(4,
new TreeNode(2, new TreeNode(1), new TreeNode(3)),
new TreeNode(6, new TreeNode(5)));
// Recursion keeps its place implicitly, on the call stack. Doing it by hand
// means the stack holds the nodes whose LEFT side is done but which have not
// themselves been visited yet.
static List<int> InOrderIterative(TreeNode? root, bool trace)
{
List<int> outp = [];
Stack<TreeNode> st = [];
TreeNode? cur = root;
while (cur is not null || st.Count > 0)
{
while (cur is not null) // go as far left as possible
{
st.Push(cur);
if (trace) Console.WriteLine($" push {cur.Value} stack=[{string.Join(",", st.Select(x => x.Value).Reverse())}]");
cur = cur.Left;
}
cur = st.Pop(); // nothing further left: visit
outp.Add(cur.Value);
if (trace) Console.WriteLine($" pop {cur.Value} visit -> [{string.Join(" ", outp)}]");
cur = cur.Right; // then handle the right subtree
}
return outp;
}
var got = InOrderIterative(tree, true);
Console.WriteLine($"\nin-order: {string.Join(" ", got)}");
Console.WriteLine($"sorted: {got.SequenceEqual(got.Order())} <- it is a BST, so in-order is sorted");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}输出：
push 4 stack=[4]
push 2 stack=[4,2]
push 1 stack=[4,2,1]
pop 1 visit -> [1]
pop 2 visit -> [1 2]
push 3 stack=[4,3]
pop 3 visit -> [1 2 3]
pop 4 visit -> [1 2 3 4]
push 6 stack=[6]
push 5 stack=[6,5]
pop 5 visit -> [1 2 3 4 5]
pop 6 visit -> [1 2 3 4 5 6]
in-order: 1 2 3 4 5 6
sorted: True <- it is a BST, so in-order is sorted栈里放的是：左子树已经处理完、自己还没被访问的节点。 调用栈原本隐式保存的，正是这些。这句话记住了，循环就只有一种写法：
- 一路向左，把经过的节点全部入栈。
- 左边走到头了？弹出一个节点并访问它。按照构造方式，它的左边一定已经处理完。
- 然后转到它的右孩子，回到第 1 步。
外层条件是 cur is not null || st.Count > 0，两半都不能少。栈可能是空的，但还有右子树要往下走：一开始就是这样，推演里到节点 4 时又是这样。
代价： O(n) 时间，O(h) 空间。空间一样，但放在堆上，不会搞垮进程。
适用场景： 树可能很深，或者题目要求遍历能暂停、再继续。BST 迭代器就是把这个循环从中间拆开。
模式 58 — 层序遍历
到目前为止，每个模式都是深度优先。层序遍历是广度优先，用的就是第 7 篇里的队列，只多了一样东西。
问题在于：队列只是一条扁平的序列，根本不知道什么是层。第 1 层还没出队完，第 2 层的节点就已经入队，全都混在一起。
队列不知道层的存在，它只是一条扁平的序列。层的边界要靠快照找回来：记下这一层开始时队列里有多少个节点在等。
// 1
// / \
// 2 3
// / \ \
// 4 5 6
// /
// 7
TreeNode tree = new(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(7))),
new TreeNode(3, null, new TreeNode(6)));
// The queue naturally mixes levels together. Capturing Count BEFORE the inner
// loop is what puts the boundaries back.
static List<List<int>> LevelOrder(TreeNode? root)
{
List<List<int>> levels = [];
if (root is null) return levels;
Queue<TreeNode> q = [];
q.Enqueue(root);
while (q.Count > 0)
{
int width = q.Count; // exactly this many nodes are on this level
List<int> level = [];
for (int i = 0; i < width; i++)
{
TreeNode n = q.Dequeue();
level.Add(n.Value);
if (n.Left is not null) q.Enqueue(n.Left);
if (n.Right is not null) q.Enqueue(n.Right);
}
levels.Add(level);
Console.WriteLine($"level {levels.Count - 1}: width was {width}, values [{string.Join(", ", level)}], queue now holds {q.Count}");
}
return levels;
}
var levels = LevelOrder(tree);
Console.WriteLine($"\nlevels: [{string.Join("], [", levels.Select(l => string.Join(", ", l)))}]");
Console.WriteLine($"depth: {levels.Count}");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}输出：
level 0: width was 1, values [1], queue now holds 2
level 1: width was 2, values [2, 3], queue now holds 3
level 2: width was 3, values [4, 5, 6], queue now holds 1
level 3: width was 1, values [7], queue now holds 0
levels: [1], [2, 3], [4, 5, 6], [7]
depth: 4全部诀窍就是内层循环之前的 int width = q.Count;。这个快照就是本层的节点数，正好出队这么多个，边界就对了。
如果写成 for (int i = 0; i < q.Count; i++)，每次迭代都会重新拿条件去比一个正在变长的队列，因为子节点不断入队。这一层永远结束不了，你只会得到一个扁平的列表。上面的推演里，数量在一层中间从 2 变成了 3，出错的正是这里。
代价： O(n) 时间，O(w) 空间，w 是最宽那一层的宽度。
适用场景： 题目里提到层、深度或最近。尤其是最小深度，应该用 BFS 而不是 DFS：BFS 碰到第一个叶子就能停，DFS 得把整棵树走完。
模式 59 — 锯齿形、左右视图，以及其他
有了层序遍历，很多树的题目只要在它上面再加一行。
TreeNode tree = new(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(7))),
new TreeNode(3, null, new TreeNode(6)));
static List<List<int>> Levels(TreeNode? root)
{
List<List<int>> levels = [];
if (root is null) return levels;
Queue<TreeNode> q = [];
q.Enqueue(root);
while (q.Count > 0)
{
int width = q.Count;
List<int> level = [];
for (int i = 0; i < width; i++)
{
TreeNode n = q.Dequeue();
level.Add(n.Value);
if (n.Left is not null) q.Enqueue(n.Left);
if (n.Right is not null) q.Enqueue(n.Right);
}
levels.Add(level);
}
return levels;
}
var levels = Levels(tree);
// Zigzag: do NOT alternate the traversal. Reverse alternate rows afterwards.
var zigzag = levels.Select((l, i) => i % 2 == 1 ? Enumerable.Reverse(l).ToList() : l).ToList();
// Right side view: the last value of each level.
var rightView = levels.Select(l => l[^1]).ToList();
// Left side view is the first of each level, for free.
var leftView = levels.Select(l => l[0]).ToList();
Console.WriteLine($"levels : [{string.Join("], [", levels.Select(l => string.Join(", ", l)))}]");
Console.WriteLine($"zigzag : [{string.Join("], [", zigzag.Select(l => string.Join(", ", l)))}]");
Console.WriteLine($"right view : {string.Join(", ", rightView)}");
Console.WriteLine($"left view : {string.Join(", ", leftView)}");
Console.WriteLine($"max depth : {levels.Count}");
Console.WriteLine($"widest : {levels.Max(l => l.Count)} nodes, at level {levels.FindIndex(l => l.Count == levels.Max(x => x.Count))}");
Console.WriteLine();
Console.WriteLine("Every one of these is the level list plus one line. Trying to build");
Console.WriteLine("zigzag by alternating the traversal itself is where people tie themselves");
Console.WriteLine("in knots — the queue order stays the same, only the output is reversed.");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}输出：
levels : [1], [2, 3], [4, 5, 6], [7]
zigzag : [1], [3, 2], [4, 5, 6], [7]
right view : 1, 3, 6, 7
left view : 1, 2, 4, 7
max depth : 4
widest : 3 nodes, at level 2
Every one of these is the level list plus one line. Trying to build
zigzag by alternating the traversal itself is where people tie themselves
in knots — the queue order stays the same, only the output is reversed.锯齿形遍历最容易把人绕晕，因为直觉是去交替改变遍历本身：奇数层先入右再入左，或者把队列换成栈。这样能做出来，但很繁琐，也很容易写错。
队列的顺序根本不用变。照常建好每一层，再把隔行的层反转。答案一样，只有一行，没什么可调试的。
左右视图就是每层的最后一个和第一个元素。最大深度就是层数。最宽的一层就是一个 Max。这些都不需要单独的算法。
适用场景： 问题是按层来问的。先建好各层，再对这个列表回答问题。
模式 60 — 用两种遍历结果重建二叉树
给定前序和中序遍历，重建这棵树。
一种遍历永远不够：很多不同的树有相同的前序。有两种，而且其中一种是中序，树就唯一确定了。
在中序数组里找根的位置，要用字典，不要扫描。扫描会让每一层都是 O(n)，在退化的树上整个重建就成了 O(n²)，而测试用的恰恰就是这种输入。
int[] preorder = [1, 2, 4, 5, 3, 6];
int[] inorder = [4, 2, 5, 1, 6, 3];
// pre-order gives you the ROOT first. in-order tells you how much of the rest
// belongs on each side of it. A dictionary makes "where is the root in inorder"
// O(1) instead of a scan, which is the difference between O(n) and O(n^2).
Dictionary<int, int> where = inorder.Select((v, i) => (v, i)).ToDictionary(t => t.v, t => t.i);
int cursor = 0;
TreeNode? Build(int lo, int hi, int depth)
{
if (lo > hi) return null;
int value = preorder[cursor++];
int mid = where[value];
Console.WriteLine($"{new string(' ', depth * 2)}root {value}: inorder[{lo}..{hi}], splits at {mid} " +
$"-> left [{lo}..{mid - 1}], right [{mid + 1}..{hi}]");
var node = new TreeNode(value);
node.Left = Build(lo, mid - 1, depth + 1); // must come first: it consumes
node.Right = Build(mid + 1, hi, depth + 1); // the pre-order cursor in order
return node;
}
TreeNode? root = Build(0, inorder.Length - 1, 0);
static void Pre(TreeNode? n, List<int> o) { if (n is null) return; o.Add(n.Value); Pre(n.Left, o); Pre(n.Right, o); }
static void In(TreeNode? n, List<int> o) { if (n is null) return; In(n.Left, o); o.Add(n.Value); In(n.Right, o); }
List<int> p = [], i = [];
Pre(root, p); In(root, i);
Console.WriteLine($"\nrebuilt pre-order: {string.Join(" ", p)} matches: {p.SequenceEqual(preorder)}");
Console.WriteLine($"rebuilt in-order : {string.Join(" ", i)} matches: {i.SequenceEqual(inorder)}");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}输出：
root 1: inorder[0..5], splits at 3 -> left [0..2], right [4..5]
root 2: inorder[0..2], splits at 1 -> left [0..0], right [2..2]
root 4: inorder[0..0], splits at 0 -> left [0..-1], right [1..0]
root 5: inorder[2..2], splits at 2 -> left [2..1], right [3..2]
root 3: inorder[4..5], splits at 5 -> left [4..4], right [6..5]
root 6: inorder[4..4], splits at 4 -> left [4..3], right [5..4]
rebuilt pre-order: 1 2 4 5 3 6 matches: True
rebuilt in-order : 4 2 5 1 6 3 matches: True靠的是两点。
前序里第一个还没用掉的值，永远是下一个根。 一个共享的游标向前推进，所以 Build(left) 必须在 Build(right) 之前调用：左子树要先用掉它那一份前序值。把这两行对调，建出来的树就是镜像，而且不报任何错。
中序告诉你在哪里切分。 根位置左边的全部属于左子树，右边的全部属于右子树。where 字典让这次查找变成 O(1)；如果改成扫描中序数组，在退化的树上整个重建就是 O(n²)，而测试用例偏偏就会挑这种输入。
注意基准情况 lo > hi 处理了推演里的空区间：[0..-1] 和 [2..1] 就是缺失的子节点在“报到”。
后序加中序也是同样的做法：倒着消费后序，并且先建右子树再建左子树。前序加后序不能唯一确定一棵树。
代价： O(n) 时间和空间。
适用场景： 题目给了你两种遍历结果，或者要序列化、反序列化一棵树。
要点
- 三种顺序只差一行。 关键在于处理节点时，子节点的答案出来了没有。
- 中序遍历 BST 得到有序序列。 这就是定义，只是走了一遍。
- 迭代写法的栈里放的是“左边已完成、自己未访问”。 说清楚不变式，代码自然就有了；死记代码，一紧张就忘。
- 处理一层之前，先把
q.Count存进局部变量。 在循环条件里反复读它，这一层就永远结束不了。 - 锯齿形不要去交替改变遍历。 建好各层，再反转隔行。
- 先建左子树，再建右子树。 两者共用一个前序游标，这两次调用的先后顺序，就是一棵树和它的镜像之间的全部区别。
- 用字典给中序数组建索引。 扫描会把 O(n) 变成 O(n²)，而测试恰恰会挑这种输入。
第 13 篇讲走到每个节点之后要做的事：路径和、直径、祖先，以及递归“返回什么”和“向下传什么”的区别。