C# 树的 DFS：路径和、直径与祖先

几乎所有树的题目都归结为一个问题：这个量是沿着树向下传，还是向上返回？路径和、不经过根的直径、最近公共祖先，以及人人第一次都会写错的二叉搜索树校验。

第 12 篇讲了怎样走到每个节点。这一篇讲走到之后要算什么，而这些内容几乎都归结为一个区别。

下面每个程序都是完整的，都在 .NET 10 上跑过，输出直接从运行结果里复制。

模式 61 — 从根到叶子的路径

收集从根到叶子的每一条路径，并找出和等于目标值的那些。

当前路径没法向上返回，因为它是来自上方的信息。所以它要向下传，放在一个列表里：进入节点时加进去，离开时再删掉。

//           5
//         /   \
//        4     8
//       /     / \
//      11   13   4
//     /  \        \
//    7    2        1
TreeNode tree = new(5,
    new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))),
    new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1))));

// The path so far is CARRIED DOWN in a list that is mutated and then undone.
// That undo is the same move backtracking is built on — see part 15.
static void Paths(TreeNode? n, List<int> path, List<string> found, int target)
{
    if (n is null) return;

    path.Add(n.Value);

    bool isLeaf = n.Left is null && n.Right is null;
    if (isLeaf)
    {
        int sum = path.Sum();
        string mark = sum == target ? "  <- sums to " + target : "";
        found.Add($"{string.Join(" -> ", path),-22} = {sum,3}{mark}");
    }
    else
    {
        Paths(n.Left, path, found, target);
        Paths(n.Right, path, found, target);
    }

    path.RemoveAt(path.Count - 1);          // undo, so a sibling starts clean
}

List<string> found = [];
Paths(tree, [], found, 22);
foreach (string s in found) Console.WriteLine(s);

Console.WriteLine();
Console.WriteLine("A leaf is a node with NO children. A node with one child is not a leaf,");
Console.WriteLine("which is why 8 -> 4 -> 1 is a path and 8 -> 4 is not.");

class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
    public int Value = value;
    public TreeNode? Left = left, Right = right;
}

输出：

5 -> 4 -> 11 -> 7      =  27
5 -> 4 -> 11 -> 2      =  22  <- sums to 22
5 -> 8 -> 13           =  26
5 -> 8 -> 4 -> 1       =  18

A leaf is a node with NO children. A node with one child is not a leaf,
which is why 8 -> 4 -> 1 is a path and 8 -> 4 is not.

递归调用之后的 path.RemoveAt(path.Count - 1) 就是这个模式的全部。没有这一行，列表会留下访问过的每一个节点，第二条路径就错了。第 15 篇的回溯全都建立在这种“先加、再撤销”的结构上，值得先在这个小例子里认出来。

另一个坑是叶子的定义。叶子是一个孩子都没有的节点。 只有一个孩子的节点不是叶子，所以输出里没有 8 -> 4，却有 8 -> 4 -> 1。如果写成 if (n.Left is null) return path.Sum();，就把只有一个孩子的节点当成了叶子，得到的短路径看起来几乎是对的。

代价： 访问 O(n) 个节点；如果把每条路径都实际生成出来，总共 O(n·h)。

适用场景： 答案是关于从根出发的完整路线：路径总和、所有路径、从叶子开始的最小字符串。

模式 62 — 递归返回什么，向下传什么

这一篇剩下的内容都建立在这个想法上。

TreeNode tree = new(5,
    new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))),
    new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1))));

// CARRIED DOWN: the parameter. Information flowing from the root towards leaves.
static void CarryDown(TreeNode? n, int depth, List<string> log)
{
    if (n is null) return;
    log.Add($"  node {n.Value,2} is at depth {depth}");
    CarryDown(n.Left, depth + 1, log);
    CarryDown(n.Right, depth + 1, log);
}

// RETURNED UP: the return value. Information flowing from leaves to the root.
static int ReturnUp(TreeNode? n)
{
    if (n is null) return 0;
    int left = ReturnUp(n.Left);
    int right = ReturnUp(n.Right);
    return 1 + Math.Max(left, right);       // needs BOTH children's answers first
}

List<string> log = [];
CarryDown(tree, 0, log);
Console.WriteLine("carried down (a parameter) — depth of each node:");
foreach (string s in log) Console.WriteLine(s);

Console.WriteLine($"\nreturned up (a return value) — height of the tree: {ReturnUp(tree)}");

Console.WriteLine();
Console.WriteLine("Depth is known on the way DOWN, before any child is examined.");
Console.WriteLine("Height is only known on the way UP, after both children have answered.");
Console.WriteLine("Deciding which one a quantity is tells you where the line goes.");

class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
    public int Value = value;
    public TreeNode? Left = left, Right = right;
}

输出：

carried down (a parameter) — depth of each node:
  node  5 is at depth 0
  node  4 is at depth 1
  node 11 is at depth 2
  node  7 is at depth 3
  node  2 is at depth 3
  node  8 is at depth 1
  node 13 is at depth 2
  node  4 is at depth 2
  node  1 is at depth 3

returned up (a return value) — height of the tree: 4

Depth is known on the way DOWN, before any child is examined.
Height is only known on the way UP, after both children have answered.
Deciding which one a quantity is tells you where the line goes.

深度在向下的路上就知道了。到达一个节点时，你已经知道走了多远，而子节点一个都还没看。它是参数。

高度只有在向上的路上才知道。两个子节点都报上来之前，你说不出这棵子树有多高。它是返回值。

判断你要算的量属于哪一种，就知道那一行该写在函数里的什么位置：递归调用之前，还是之后。这一篇的每道题，都是在回答这同一个问题：

量	方向
深度、当前路径、合法范围	向下传，作为参数
高度、子树和、节点数	向上返回，作为值
直径、“树中任意位置的最优”类答案	向上返回，并且记录在函数外面

第三行就是下一个模式。

模式 63 — 直径：答案是副作用

任意两个节点之间最长的路径。难点在于它不一定经过根，而且经常不经过。

//         1
//       /   \
//      2     3
//     / \
//    4   5
//   /     \
//  6       7
TreeNode tree = new(1,
    new TreeNode(2, new TreeNode(4, new TreeNode(6)), new TreeNode(5, null, new TreeNode(7))),
    new TreeNode(3));

// The longest path in a tree need not pass through the root. At every node the
// best path THROUGH it is left height + right height. The answer is the largest
// of those — which is a SIDE EFFECT of a function that returns something else.
int best = 0;

int Height(TreeNode? n, int depth)
{
    if (n is null) return 0;
    int left = Height(n.Left, depth + 1);
    int right = Height(n.Right, depth + 1);

    int through = left + right;                 // edges, counting through this node
    if (through > best)
    {
        best = through;
        Console.WriteLine($"{new string(' ', depth * 2)}node {n.Value}: left={left} right={right} -> path of {through} edges through it (new best)");
    }
    else
    {
        Console.WriteLine($"{new string(' ', depth * 2)}node {n.Value}: left={left} right={right} -> {through} edges, best stays {best}");
    }

    return 1 + Math.Max(left, right);           // the RETURN value is the height
}

Height(tree, 0);
Console.WriteLine($"\ndiameter: {best} edges");
Console.WriteLine("the path is 6 -> 4 -> 2 -> 5 -> 7, which never touches the root");

class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
    public int Value = value;
    public TreeNode? Left = left, Right = right;
}

输出：

      node 6: left=0 right=0 -> 0 edges, best stays 0
    node 4: left=1 right=0 -> path of 1 edges through it (new best)
      node 7: left=0 right=0 -> 0 edges, best stays 1
    node 5: left=0 right=1 -> 1 edges, best stays 1
  node 2: left=2 right=2 -> path of 4 edges through it (new best)
  node 3: left=0 right=0 -> 0 edges, best stays 4
node 1: left=3 right=1 -> 4 edges, best stays 4

diameter: 4 edges
the path is 6 -> 4 -> 2 -> 5 -> 7, which never touches the root

在每个节点，经过这个节点的最长路径是 leftHeight + rightHeight。所以一边遍历树、一边计算高度，并在每个节点检查经过它的路径是否超过目前的最优值。

函数返回的是高度，直径记在函数外面的变量里。这是两个不同的量，函数只返回其中一个。第一次看到时觉得别扭，原因就在这里。如果试图返回直径，就会乱成一团，因为父节点需要的是子节点的高度，不是子节点的最优路径。

看推演。最优值是在节点 2 定下来的，根报告 4 条边，但没有更新它。答案是 6 -> 4 -> 2 -> 5 -> 7，节点 1 不在上面。

代价： O(n)，一遍。

适用场景： 答案是“整棵树里任意位置的最优”，而不是“从根出发的最优”：二叉树中的最大路径和、最长同值路径、最大 BST 子树。都是同一种结构。

模式 64 — 最近公共祖先

两个目标节点都在它下面的、最深的那个节点。

//         3
//       /   \
//      5     1
//     / \   / \
//    6   2 0   8
//       / \
//      7   4
TreeNode tree = new(3,
    new TreeNode(5, new TreeNode(6), new TreeNode(2, new TreeNode(7), new TreeNode(4))),
    new TreeNode(1, new TreeNode(0), new TreeNode(8)));

// Return the node itself if found, otherwise whatever the children found.
// A node that hears back from BOTH sides is the meeting point.
static TreeNode? Lca(TreeNode? n, int a, int b)
{
    if (n is null) return null;
    if (n.Value == a || n.Value == b) return n;      // found one; stop descending

    TreeNode? left = Lca(n.Left, a, b);
    TreeNode? right = Lca(n.Right, a, b);

    if (left is not null && right is not null) return n;   // one on each side
    return left ?? right;                                   // pass the survivor up
}

foreach ((int a, int b) in new[] { (5, 1), (5, 4), (7, 4), (6, 8), (5, 5) })
    Console.WriteLine($"lca({a}, {b}) = {Lca(tree, a, b)!.Value}");

Console.WriteLine();
Console.WriteLine("lca(5, 4) is 5: a node is allowed to be its own ancestor, which is why");
Console.WriteLine("the search stops the moment it finds either value rather than going deeper.");

Console.WriteLine();
// In a BST you do not need any of that — the values tell you which way to go.
static TreeNode? LcaBst(TreeNode? n, int a, int b)
{
    while (n is not null)
    {
        if (a < n.Value && b < n.Value) n = n.Left;
        else if (a > n.Value && b > n.Value) n = n.Right;
        else return n;                    // they diverge here, or one IS here
    }
    return null;
}

TreeNode bst = new(6,
    new TreeNode(2, new TreeNode(0), new TreeNode(4, new TreeNode(3), new TreeNode(5))),
    new TreeNode(8, new TreeNode(7), new TreeNode(9)));
Console.WriteLine("in a BST, no recursion is needed at all:");
foreach ((int a, int b) in new[] { (2, 8), (2, 4), (3, 5) })
    Console.WriteLine($"  lca({a}, {b}) = {LcaBst(bst, a, b)!.Value}");

class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
    public int Value = value;
    public TreeNode? Left = left, Right = right;
}

输出：

lca(5, 1) = 3
lca(5, 4) = 5
lca(7, 4) = 2
lca(6, 8) = 3
lca(5, 5) = 5

lca(5, 4) is 5: a node is allowed to be its own ancestor, which is why
the search stops the moment it finds either value rather than going deeper.

in a BST, no recursion is needed at all:
  lca(2, 8) = 6
  lca(2, 4) = 2
  lca(3, 5) = 4

三行代码包揽一切。

如果当前节点就是某个目标，直接返回它，不再往下找。否则去问两个子节点。如果两边都返回非空，说明两个目标分在两侧，当前节点就是交汇点。否则把找到的那一个向上传。

lca(5, 4) 返回 5 不是 bug。节点算作自己的祖先，这是通常的定义，也正因为如此，搜索一找到任何一个值就停下，不再继续往下。

在 BST 里，这些都不需要。一路向下比较：两个目标都比当前值小就往左，都比它大就往右，第一个让两者分开的节点，或者本身就是其中一个目标的节点，就是答案。不用递归，O(h) 时间，O(1) 空间。

代价： 一般情况 O(n)，BST 上 O(h)。

适用场景： 问题关于祖先关系，或者两个节点之间的距离，即 depth(a) + depth(b) - 2 * depth(lca)。

模式 65 — 校验二叉搜索树

几乎人人第一次都会写错的一道题。

//      5              5 is the root, and 4 sits in its RIGHT subtree.
//     / \             Every parent-child pair is individually fine.
//    1   6            The tree is still not a BST.
//       / \
//      4   7
TreeNode broken = new(5,
    new TreeNode(1),
    new TreeNode(6, new TreeNode(4), new TreeNode(7)));

TreeNode fine = new(5,
    new TreeNode(3, new TreeNode(1), new TreeNode(4)),
    new TreeNode(8, new TreeNode(6), new TreeNode(9)));

// WRONG: only compares a node with its immediate children.
static bool NaiveCheck(TreeNode? n)
{
    if (n is null) return true;
    if (n.Left is not null && n.Left.Value >= n.Value) return false;
    if (n.Right is not null && n.Right.Value <= n.Value) return false;
    return NaiveCheck(n.Left) && NaiveCheck(n.Right);
}

// RIGHT: every node inherits a range from its ancestors, and must fall inside it.
static bool Check(TreeNode? n, long low, long high)
{
    if (n is null) return true;
    if (n.Value <= low || n.Value >= high) return false;
    return Check(n.Left, low, n.Value) && Check(n.Right, n.Value, high);
}

foreach ((string name, TreeNode t) in new[] { ("broken", broken), ("fine  ", fine) })
    Console.WriteLine($"{name}   naive says {NaiveCheck(t),-5}   bounds say {Check(t, long.MinValue, long.MaxValue)}");

Console.WriteLine();
Console.WriteLine("The naive check passes the broken tree because 4 < 6 and 6 > 5 are both");
Console.WriteLine("true locally. Nothing ever told 4 that it had to be greater than 5.");
Console.WriteLine();
Console.WriteLine("Bounds narrow on the way down: going left caps the maximum at the node's");
Console.WriteLine("value, going right raises the minimum to it. That is carried-down");
Console.WriteLine("information, exactly like depth.");
Console.WriteLine();
Console.WriteLine("long is used for the bounds so a node holding int.MinValue still works.");

class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
    public int Value = value;
    public TreeNode? Left = left, Right = right;
}

输出：

broken   naive says True    bounds say False
fine     naive says True    bounds say True

The naive check passes the broken tree because 4 < 6 and 6 > 5 are both
true locally. Nothing ever told 4 that it had to be greater than 5.

Bounds narrow on the way down: going left caps the maximum at the node's
value, going right raises the minimum to it. That is carried-down
information, exactly like depth.

long is used for the bounds so a node holding int.MinValue still works.

朴素版本只把每个节点和它的直接孩子比较，结果放过了一棵不是 BST 的树。在这棵树里，4 < 6 成立，6 > 5 也成立，所以每一次局部检查都通过。但 4 在根的右子树里，必须大于 5，而局部检查从来不会说出这一点。

解决办法是向下传的信息，和深度完全一样。每个节点都从祖先那里继承一个范围。往左走，上界压到当前值；往右走，下界抬到当前值。节点落在继承的范围之外，就不合法。

还有两个细节。边界用的是 long，这样值为 int.MinValue 的节点仍然可以比较；如果用 int，哨兵值就会和合法的值撞在一起。另外比较是严格的，因为通常定义下的 BST 没有重复值。

代价： O(n) 时间，O(h) 空间。

适用场景： 要校验的结构性质取决于所有祖先，而不只是父节点。“这是不是合法的堆”“每个节点是否都比它上方的所有节点小”，都是同一种结构。

要点

• 先问这个量是向下走还是向上走。 向下就是参数，向上就是返回值。这一个问题能解决大多数树的题目。
• 递归调用之后要撤销。 path.RemoveAt(path.Count - 1) 不是收拾整洁，而是兄弟节点的路径能算对的前提。
• 叶子没有孩子。 只有一个孩子的节点不是叶子，把它当成叶子，会悄无声息地得到过短的路径。
• 直径是副作用，不是返回值。 函数返回高度，另外单独记录最优值，因为父节点需要的是子节点的高度。
• 最长路径经常不经过根。 如果你的解法只考虑经过根的路径，在大多数树上都是错的。
• 节点是自己的祖先。 lca(a, a) 就是 a，提前返回实现的正是这一点。
• 校验 BST 需要范围，而不是和父节点比较。 局部检查会放过不是 BST 的树，而且不声不响。

第 14 篇离开树，转向区间。那里全部的难点，就在于按起点排序还是按终点排序。