二叉树的最大路径和

Terence888

1. # Definition for a binary tree node.
   
2. # class TreeNode:
   
3. #     def __init__(self, val=0, left=None, right=None):
   
4. #         self.val = val
   
5. #         self.left = left
   
6. #         self.right = right
   
7. class Solution:
   
8.     def maxPathSum(self, root: Optional[TreeNode]) -> int:
   
9.         self.res = 0 #初始化全局变量
   
10.         def helper(node):
    
11.             if not node: return 0 #如果没有节点（是叶子结点），返回0
    
12.             self.res = max(self.res,(helper(node.left) + helper(node.right) + node.val)) #结果为左右子树最大权值加上根节点的值
    
13.             return max(0,max(helper(node.left),helper(node.right)) + node.val)#最大值为左右子树
    
14.         helper(root)
    
15.         return self.res

复制代码

帮我逐层分析一下，尤其不懂helper函数的返回值为什么是

1. max(0,max(helper(node.left),helper(node.right)) + node.val)

复制代码

其中，

1. root =
   
2. [-10,9,20,null,null,15,7]

复制代码

FishC

好的，我们来逐层分析这个程序，尤其是 `helper` 函数。

### 目标
我们需要找到二叉树中的最大路径和，路径可以从任何节点开始和结束。

### 程序解析

1. **类和函数定义**

  

1. class Solution:
   
2.        def maxPathSum(self, root: Optional) -> int:
   
3.            self.res = float('-inf')  # 初始化最大值为负无穷
   
4.            def helper(node):
   
5.                if not node:
   
6.                    return 0
   
7.                ...
   
8.            ...

复制代码

   `maxPathSum` 函数调用 `helper` 函数，递归计算路径和值。

2. **`helper` 函数**

  

1. def helper(node):
   
2.        if not node:
   
3.            return 0

复制代码

   - 如果 `node` 是 `None`，返回 0，因为空节点的贡献为 0。

3. **递归计算**

  

1. left = max(0, helper(node.left))
   
2.    right = max(0, helper(node.right))

复制代码

   - 对于每一个 `node`，计算其左子树和右子树的最大贡献路径和。
   - `max(0, ...)` 的作用是忽略负路径，只考虑非负路径。

4. **更新全局最大路径和**

  

1. self.res = max(self.res, left + right + node.val)

复制代码

   - 计算通过当前 `node` 的路径和，包括其值、左子树贡献和右子树贡献，并更新全局最大值 `self.res`。

5. **返回值**

  

1. return max(left, right) + node.val

复制代码

   - 返回以当前节点为根的最大路径贡献，即当前节点值加上左/右子树中较大的路径贡献。
   - 这个返回值供递归调用的父节点使用。

### 总结

- `helper` 函数的返回值并不是当前节点的最大路径和，而是给父节点提供的最大路径贡献值。
- `self.res` 是全局变量，存储到目前为止的最大路径和，包括从任意节点开始和结束的路径。

这种方法有效利用了递归遍历了二叉树的所有节点，最后我们得到了最大路径和。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。