二叉树中的最大路径和

pythonCopy codeclass TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        # 初始化最大路径和为负无穷大
        self.max_sum = float('-inf')
        
        def max_gain(node):
            if not node:
                return 0
            
            # 递归计算左右子树的最大贡献值
            left_gain = max(max_gain(node.left), 0)  # 如果左子树贡献为负，取0
            right_gain = max(max_gain(node.right), 0)  # 如果右子树贡献为负，取0
            
            # 当前节点的最大路径和
            current_max_path = node.val + left_gain + right_gain
            
            # 更新全局最大路径和
            self.max_sum = max(self.max_sum, current_max_path)
            
            # 返回当前节点的单边最大贡献值
            return node.val + max(left_gain, right_gain)
        
        # 开始递归
        max_gain(root)
        return self.max_sum

3. 算法详解

max_gain函数：这个函数计算当前节点的最大贡献值。如果子节点的贡献是负值，则贡献为0（因为负值只会减小路径和）。然后我们计算当前节点的最大路径和并更新全局的最大值。
递归思路：通过递归的方式，自底向上计算每个节点的最大贡献值，并且在递归的过程中更新全局的最大路径和。
关键点：最大路径和的更新是 当前节点值 + 左子树贡献 + 右子树贡献，因为这是包含当前节点和其左右子树的完整路径。

4. 举例说明

假设有这样一棵二叉树：

markdownCopy code       1
      / \
     2   3

左子树的最大贡献是 2，右子树的最大贡献是 3。
当前节点 1 的最大路径和是 1 + 2 + 3 = 6，因此最大路径和是 6。

5. 复杂度分析

时间复杂度：O(n)，其中 n 是二叉树中的节点个数。每个节点都被访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归栈的深度由树的高度决定。

这个算法高效且易于理解，可以处理树中任意形状的路径，并找到其最大和。

二叉树最长同值路径的长度

You said:

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。注意：两个节点之间的路径长度由它们之间的边数表示。

ChatGPT said:

ChatGPT

我们要找到最长的路径，其中所有节点值相同。这条路径可以经过任意节点，也可以不经过根节点，计算时路径的长度指的是边数而不是节点数。

1. 算法思路

为了找到最长路径，思路是**深度优先搜索（DFS）**遍历二叉树，递归计算每个节点为起点的最长同值路径，并同时更新全局的最长路径。

核心步骤：

对于每个节点，我们递归计算左右子树中的最长同值路径。
如果左子节点的值等于当前节点的值，说明左边可以延伸路径长度；如果右子节点的值等于当前节点的值，右边也可以延伸路径。
每个节点的最大路径长度是左边路径长度 + 右边路径长度。
同时，我们需要更新一个全局变量 max_len，记录当前发现的最长路径长度。

2. 代码实现

pythonCopy codeclass TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def longestUnivaluePath(self, root: TreeNode) -> int:
        self.max_len = 0
        
        def dfs(node):
            if not node:
                return 0
            
            # 递归计算左右子树的最长同值路径
            left_len = dfs(node.left)
            right_len = dfs(node.right)
            
            # 初始化左右同值路径长度为0
            left_arrow = right_arrow = 0
            
            # 如果左子节点的值与当前节点值相同，左边路径可以延伸
            if node.left and node.left.val == node.val:
                left_arrow = left_len + 1
                
            # 如果右子节点的值与当前节点值相同，右边路径可以延伸
            if node.right and node.right.val == node.val:
                right_arrow = right_len + 1
            
            # 更新全局最长路径为左右同值路径之和
            self.max_len = max(self.max_len, left_arrow + right_arrow)
            
            # 返回当前节点为起点的最长同值路径
            return max(left_arrow, right_arrow)
        
        dfs(root)
        return self.max_len

3. 算法详解

DFS递归函数：递归地访问每个节点，计算其左子树和右子树的最长同值路径。
- left_arrow：表示从左子节点向下的同值路径长度，如果左子节点的值和当前节点的值相同，才可以延续这个路径。
- right_arrow：表示从右子节点向下的同值路径长度，同理，右子节点值相同才可以延续路径。
路径更新：对于每个节点，可能的最长路径是左同值路径长度 + 右同值路径长度，这是该节点作为中心连接左右的最大可能路径。
返回值：我们递归返回的是以当前节点为起点的最长同值路径（从当前节点往左或往右延伸的较长一条路径）。

4. 复杂度分析

时间复杂度：O(n)，其中 n 是二叉树中的节点个数。每个节点都会被访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归栈的最大深度就是树的高度。

5. 例子

假设我们有以下二叉树：

markdownCopy code       5
      / \
     4   5
    / \   \
   1   1   5

这棵树中最长的路径是两个5节点之间的路径，路径长度为2（边数）。
经过DFS递归，更新最长路径值为2，最终返回结果。

这个方法使用DFS递归，易于理解，同时保证了每个节点的路径只计算一次，因此效率较高。