【LeetCode】第124题：二叉树的最大路径和

约定不等于承诺〃 2021-12-12 00:27 221阅读 0赞

LeetCode 链接：[https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/][https_leetcode-cn.com_problems_binary-tree-maximum-path-sum]

本题可以对比左神算法中的：**[二叉树中的最远距离][Link 1]**，只不过最远距离中没有考虑权重的问题，本题需要考虑每个节点的权重问题，还是有所区别的。

**题目：给定一个非空二叉树，返回其最大路径和。**

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

> 示例 1:
> 
> 输入: \[1,2,3\]
> 
>        **1**  
>       /  \\  
>      **2   3**
> 
> 输出: 6  
> 示例 2:
> 
> 输入: \[-10,9,20,null,null,15,7\]
> 
>    -10  
>    /   \\  
>   9  **20**  
>      /   \\  
>    **15   7**
> 
> 输出: 42

根据题意，最大路径和可能出现在：**左子树中、右子树中、包含根节点与左右子树中**。我们的思路是递归从 bottom 向 top return 的过程中，记录左子树和右子树中路径更大的那个，并向父节点提供当前节点和子树组成的最大值。

递归设计：

1、返回值：(root.val) + max(left, right) 即此节点与左右子树最大值之和，较差的解直接被舍弃，不会再被用到。

*  需要注意的是，若计算结果 tmp <= 0，意味着对根节点有负贡献，不会在任何情况选这条路（父节点中止），因此返回 0。

2、递归终止条件：越过叶子节点，返回 0；

3、记录最大值：**当前节点最大值 = root.val + left + right**。

4、最终返回所有路径中的全局最大值即可

public class MaxPathSum_124 {
    
        public class TreeNode{
            public int val;
            public TreeNode left;
            public TreeNode right;
    
            public TreeNode(int val){
                this.val = val;
            }
        }
    
        // maxSum代表最大路径和
        private int maxSum = Integer.MIN_VALUE;
    
        private int maxPathSum(TreeNode root){
            maxPath(root);
            return maxSum;
        }
    
        private int maxPath(TreeNode root){
            if(root == null){
                // 遇到空节点则直接返回0
                return 0;
            }
            int left = maxPath(root.left);
            int right = maxPath(root.right);
            maxSum = Math.max(left + right + root.val, maxSum);
            int temp = Math.max(left, right) + root.val;
            return temp > 0 ? temp : 0;
        }
    }

[https_leetcode-cn.com_problems_binary-tree-maximum-path-sum]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
[Link 1]: https://blog.csdn.net/pcwl1206/article/details/94601765