LeetCode_二叉树_困难_124. 二叉树中的最大路径和

港控/mmm° 2023-10-06 22:43 21阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。**该路径至少包含一个节点，且不一定经过根节点。**

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

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

**示例 1：**  
![在这里插入图片描述][c5b3d97fd78c4ec1805bb540f55274f0.png]  
输入：root = \[1,2,3\]  
输出：6  
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

**示例 2：**  
![在这里插入图片描述][3f365f3645284f3c91a4dcefa8be5b81.png]  
输入：root = \[-10,9,20,null,null,15,7\]  
输出：42  
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

**提示：**  
树中节点数目范围是 \[1, 3 \* 104\]  
\-1000 <= Node.val <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum

## 2.思路 ##

（1）后序遍历

相关题目：  
[LeetCode\_二叉树\_前缀和\_中等\_437.路径总和 III][LeetCode_437._ III]  
[LeetCode\_二叉树\_简单\_543.二叉树的直径][LeetCode_543.]

## 3.代码实现（Java） ##

//思路1————后序遍历
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
    
        int res = Integer.MIN_VALUE;
    
        public int maxPathSum(TreeNode root) {
        
            oneSideMax(root);
            return res;
        }
    
        public int oneSideMax(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            int leftMaxSum = Math.max(0, oneSideMax(root.left));
            int rightMaxSum = Math.max(0, oneSideMax(root.right));
            //后序遍历位置，顺便更新最大路径和
            int pathMaxSum = root.val + leftMaxSum + rightMaxSum;
            res = Math.max(pathMaxSum, res);
            /*
                实现函数定义，左右子树的最大单边路径和加上当前根节点的值
                就是从当前根节点 root 为起点的最大单边路径和
            */
            return Math.max(leftMaxSum, rightMaxSum) + root.val;
        }
    }

[c5b3d97fd78c4ec1805bb540f55274f0.png]: https://img-blog.csdnimg.cn/c5b3d97fd78c4ec1805bb540f55274f0.png
[3f365f3645284f3c91a4dcefa8be5b81.png]: https://img-blog.csdnimg.cn/3f365f3645284f3c91a4dcefa8be5b81.png
[LeetCode_437._ III]: https://blog.csdn.net/weixin_43004044/article/details/125011449
[LeetCode_543.]: https://xgqngu.blog.csdn.net/article/details/123890167