day52（1.2）——leetcode面试经典150

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

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

题目：

题解：

/** * 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 { private int sum = Integer.MIN_VALUE; public int dfs(TreeNode root) { if(root == null) { return 0; } //有子结点 int left = dfs(root.left); int right = dfs(root.right); // 两条链拼成路径 sum = Math.max(sum, left+right+root.val); // 当前子树最大链和（注意这里和 0 取最大值了） return Math.max(Math.max(left, right)+root.val, 0); } public int maxPathSum(TreeNode root) { dfs(root); return sum; } }