跳转至

二叉树最大路径

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

递归

树的问题一般用递归写法是最快的。

本题要求寻找最优路径。

我们只需要从根节点开始寻找即可。

假设f(node)表示以node为根节点的最大单向路径。

单向路径也有相关的题目：路径总和

f的求解可以递归完成：

f(node) = node.val + max(f(node.left), f(node.right), 0)

单向路径要么沿着左节点向下走，要么沿着右节点向下走，或者是直接断开。

知道了每个节点的最大单向路径之后，要求最大路径和就简单了：

最大路径要么是单向路径，要么是双向路径（左右单向都链接）。

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.ans = -inf
        cache = {} # 记忆，避免重复递归

        def f(node):
            """以node为根节点的【单向】最大路径"""
            if node is None:
                return 0
            elif node in cache:
                return cache[node]
            left = f(node.left)
            right = f(node.right)
            # 单向路径，要么链接左侧要么链接右侧，要么断开
            uni_path = node.val + max(0, left, right)
            # 双向路径
            bi_path = node.val + max(0, left) + max(0, right)
            # 更新全局最大路径
            self.ans = max(
                self.ans,  # 没找到更好的
                uni_path,  # 单向路径是最好的
                bi_path    # 双向路径是最好的
            )
            cache[node] = uni_path
            return uni_path

        # 在递归的过程中，所有节点都被访问了
        # 所有self.ans就是最终答案
        f(root)

        return self.ans
最后更新: 2025-05-29 02:42:18
创建日期: 2025-04-17 21:54:37

评论