### 寻找二叉树中和最大的路径 要找到从根节点到叶子节点的路径上具有最大和的路径，可以通过深度优先搜索（DFS）来实现。以下是解决问题的具体方法： #### 方法概述 1. 使用递归的方式遍历整个二叉树。 2. 对于每个节点，记录当前路径上的累加和以及路径本身。 3. 当到达叶子节点时，比较当前路径和的最大值并更新结果。 下面是完整的 Python 实现代码： ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def maxPathSum(root: TreeNode): if not root: return 0, [] # 定义全局变量用于存储最大路径和及其对应路径 max_sum = float('-inf') path = [] def dfs(node, current_path): nonlocal max_sum, path if not node: return # 添加当前节点到路径中 current_path.append(node.val) # 如果是叶子节点，则检查路径和 if not node.left and not node.right: current_sum = sum(current_path) if current_sum > max_sum: max_sum = current_sum path = list(current_path) # 复制当前路径 # 递归处理左子树和右子树 if node.left: dfs(node.left, current_path) if node.right: dfs(node.right, current_path) # 回溯：移除最后一个访问的节点 current_path.pop() dfs(root, []) return max_sum, path # 测试用例 if __name__ == "__main__": # 构建一棵简单的二叉树 tree = TreeNode(10, TreeNode(5, TreeNode(3), TreeNode(-2)), TreeNode(-3, None, TreeNode(11))) result_sum, result_path = maxPathSum(tree) print(f"最大路径和为: {result_sum} [{', '.join(map(str, result_path))}]") ``` #### 输出解释 上述代码会返回两个部分： 1. **最大路径和**：即从根节点到某个叶子节点路径上的数值之和的最大值。 2. **对应的路径**：构成该最大路径和的一系列节点值。 --- ### 关键点分析 1. **递归终止条件** 当前节点为 `None` 或者已经到达叶子节点时停止递归[^1]。 2. **回溯法的应用** 在每次递归调用结束后，需要将当前路径中的最后一位删除（即回溯），以便不影响其他分支的结果[^2]。 3. **时间复杂度与空间复杂度** - 时间复杂度：O(n)，其中 n 是节点总数，因为每个节点只被访问一次。 - 空间复杂度：O(h)，h 表示树的高度，这是由于递归栈的空间需求决定的[^5]。 --- ###