题解 | #二叉树中的最大路径和#

方法一（递归）

1.题意整理

• 给定一颗二叉树，二叉树中每个节点对应一个节点值。
• 求二叉树中的最大路径和，其中路径指的是从任意节点出发到另一个节点之间所经过的路径。

2.思路整理

对于二叉树的大部分题目，都可以试图分三种情况进行考虑，分别是当前节点的情况、当前节点左子树的情况、当前节点右子树的情况。然后我们给递归的返回值一个含义，即对应节点为根的子树的贡献值。如下图所示，对于叶子节点2和-1，贡献值直接是节点本身，对于非叶子节点1，贡献值为当前节点值加上左右子树贡献值的较大者，如果某个子树贡献值小于0，则看作0来处理。

有了所有子树的贡献值之后，求最大路径和就好办了，只要计算当前节点加上左右子树贡献值，取所有可能中的最大值即可。

• 递归终止条件：当搜索完所有路径，递归终止，即root为空。
• 递归如何传递：每次需要往左右子树方向递归，然后利用左右子树的贡献值，可以计算出以当前节点为根的子树中，经过当前节点的所有路径的最大值。
• 递归的返回值：返回以当前节点为根的子树的贡献值。

图解展示：

3.代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    //记录最终结果
    int res=Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        //为空直接返回0
        if(root==null) return 0;
        //递归
        dfs(root);
        return res;
    }
    
    private int dfs(TreeNode root){
        //递归终止条件
        if(root==null) return 0;
        //l表示左子树最大贡献值，r表示右子树最大贡献值，若小于0，则贡献值为0
        int l=Math.max(0,dfs(root.left));
        int r=Math.max(0,dfs(root.right));
        //计算当前节点值，加上左右子树贡献值，取最大的那一个
        res=Math.max(res,root.val+l+r);
        return Math.max(l,r)+root.val;
    }
}

4.复杂度分析

• 时间复杂度：需要遍历二叉树中所有节点，并且每个节点的访问次数不超过2，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：递归栈的深度为$lo{g}_{2}nlog\_2n$，当退化为链表时，深度为n，所以空间复杂度为$O(n)O(n)$。