124.二叉树中的最大路径和

题目

思路

使用深度优先搜索，使用全局变量max，分成两种情况：

• 一种是当前遍历的节点是中间的节点，计算这个节点左右子树的节点和（左右子树必须大于0，否则赋值为0），并与max比较。
  • 第二种是这个节点只作为中间路过的节点，计算左右子树的最大值（左右子树必须大于0，否则赋值为0），然后加上当前节点值 返回。

代码

class Solution {
    int max=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if(root==null){
            return 0;
        }
        helper(root);
        return max;
    }
    public int helper(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=helper(root.left);
        int right=helper(root.right);
        int temp=root.val+(Math.max(left,0)+Math.max(right,0));
        max=Math.max(max,temp);
        return root.val+Math.max(Math.max(left,0),Math.max(right,0));
    }
    
}

时间