LeetCode LCR 051. 二叉树中的最大路径和

Categories:

题目描述
思路分析
1. 解法一：后序 DFS + 全局变量记录最大值（推荐）
相似题目

题目描述

✅ LCR 051. 二叉树中的最大路径和

思路分析

解法一：后序 DFS + 全局变量记录最大值（推荐）

核心思路：

任意一条最大路径必有唯一的”拐点”节点（路径最高点），路径从左子树延伸经过该节点再延伸到右子树。因此枚举每个节点作为拐点，取全局最大值即可。

后序递归函数 dfs(node) 承担双重职责：

返回值（向上贡献）：当前节点能给父节点提供的最大路径增益 = node.val + max(0, left, right)，只能选左或右一侧延伸，路径不可分叉。

副作用（更新全局最大）：以当前节点为拐点时，路径可同时走左右两侧：res = max(res, node.val + max(0, left) + max(0, right))。

负贡献剪枝：若某子树贡献为负（< 0），不选它（取 max(0, contribution)），等价于路径在当前节点截断，不向下延伸。

初始化 res = Integer.MIN_VALUE，因为节点值可为负，不能用 0 初始化。

复杂度分析：

时间复杂度：O(n)，其中 n 为二叉树节点数，每个节点恰好访问一次。

空间复杂度：O(h)，其中 h 为树的高度，最坏情况（退化为链表）为 O(n)，递归栈深度。

class Solution {

    // 全局变量记录最大路径和，初始化为最小整数（节点值可能全为负）
    private int res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return res;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 后序遍历：先递归左右子树，负贡献直接取 0（不选该子树）
        int left = Math.max(dfs(node.left), 0);
        int right = Math.max(dfs(node.right), 0);
        // 以当前节点为拐点时，路径可同时延伸左右两侧
        res = Math.max(res, left + right + node.val);
        // 向父节点只能提供一侧的最大增益
        return node.val + Math.max(left, right);
    }
}

func maxPathSum(root *TreeNode) int {
    res := math.MinInt32

    // 后序遍历，返回当前节点向父节点提供的最大路径增益
    var dfs func(node *TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        // 递归左右子树，负贡献取 0 表示不选该子树
        left := max(dfs(node.Left), 0)
        right := max(dfs(node.Right), 0)
        // 以当前节点为拐点，更新全局最大路径和
        res = max(res, left+right+node.Val)
        // 只能选一侧延伸，返回向上的最大贡献
        return node.Val + max(left, right)
    }

    dfs(root)
    return res
}

相似题目

题目	难度	考察点
112. 路径总和	简单	二叉树、DFS
113. 路径总和 II	中等	二叉树、回溯
543. 二叉树的直径	简单	二叉树、后序 DFS
687. 最长同值路径	中等	二叉树、后序 DFS
437. 路径总和 III	中等	前缀和、DFS
1372. 二叉树中的最长交错路径	中等	二叉树、后序遍历
2246. 相邻字符不同的最长路径	困难	树形 DP、后序 DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/49132854