如何实现从文本动态加载的深度树自上而下最大路径求和？

• 构建一棵层级树：每行节点与下一行的左右两个节点相连，每行首尾节点仅与上一行对应一个节点相连
• 从指定文本文件（格式为多行空格分隔的数字）动态加载节点数值，禁止手动添加节点
• 计算树中自上而下的最大路径和

现有代码的问题 #

用户提供的C#代码存在两处核心错误：

1. Insert方法逻辑错误：采用普通二叉树的递归插入逻辑，无法构建符合需求的层级关联关系
2. GetTree方法行处理逻辑错误：遍历每行数值时，错误地将当前行的每个节点挂载到前一个节点下，而非关联上一行的正确父节点

修正后的完整实现 #

1. Node类（保持原有定义） #

public class Node
{
    public int value;
    public Node left;
    public Node right;
    public Node parent;

    public Node(int value)
    {
        this.value = value;
    }
}

2. 正确的树构建方法 #

通过逐行保存节点列表，按层级关联父节点，确保每行节点正确连接到上一行的对应节点：

using System;
using System.Collections.Generic;
using System.IO;

public class TreeBuilder
{
    public static Node BuildTreeFromFile(string filePath)
    {
        string[] lines = File.ReadAllLines(filePath);
        if (lines.Length == 0) return null;

        // 存储每一行的节点，方便后续关联父节点
        List<List<Node>> treeRows = new List<List<Node>>();

        // 初始化根节点（第一行）
        string[] firstLineVals = lines[0].Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
        if (firstLineVals.Length == 0) return null;
        
        Node root = new Node(int.Parse(firstLineVals[0]));
        treeRows.Add(new List<Node> { root });

        // 处理后续每一行
        for (int rowIdx = 1; rowIdx < lines.Length; rowIdx++)
        {
            string line = lines[rowIdx];
            if (string.IsNullOrWhiteSpace(line)) continue;

            string[] vals = line.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            // 校验行节点数：第n行（从1开始）应该有n个节点
            if (vals.Length != rowIdx + 1) return null;

            List<Node> currentRow = new List<Node>();
            List<Node> prevRow = treeRows[rowIdx - 1];

            for (int colIdx = 0; colIdx < vals.Length; colIdx++)
            {
                if (!int.TryParse(vals[colIdx], out int num)) return null;
                Node currentNode = new Node(num);
                currentRow.Add(currentNode);

                // 关联父节点：当前节点连接上一行的colIdx-1和colIdx节点（首尾节点仅一个父节点）
                if (colIdx > 0)
                {
                    Node leftParent = prevRow[colIdx - 1];
                    leftParent.right = currentNode;
                    currentNode.parent = leftParent;
                }
                if (colIdx < prevRow.Count)
                {
                    Node rightParent = prevRow[colIdx];
                    rightParent.left = currentNode;
                }
            }

            treeRows.Add(currentRow);
        }

        return root;
    }
}

3. 最大路径和计算方法 #

采用递归方式，从每个节点出发计算到叶子节点的最大路径和，最终取全局最大值：

public class MaxPathCalculator
{
    public static int GetMaxPathSum(Node root)
    {
        if (root == null) return 0;
        // 叶子节点直接返回自身值
        if (root.left == null && root.right == null) return root.value;
        
        // 递归计算左右子树的最大路径和，取较大值加上当前节点值
        int leftSum = GetMaxPathSum(root.left);
        int rightSum = GetMaxPathSum(root.right);
        
        // 非叶子节点至少有一个子节点，无需处理双空情况
        return root.value + Math.Max(leftSum, rightSum);
    }
}

测试验证 #

使用示例文本文件：

3
7 6
2 4 9
1 4 8 2

构建的树结构符合需求，最大路径为 3 → 7 → 4 → 8，总和为 3+7+4+8=22。

内容的提问来源于stack exchange，提问作者Thehurrikayne