讨论/《深度优先搜索》 - 练习:二叉树中的最大路径和/
《深度优先搜索》 - 练习:二叉树中的最大路径和
共 3 个回复
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        res = root.val
        def dfs(root):
            nonlocal res
            if not root: return 0
            L = dfs(root.left)
            R = dfs(root.right)
            res = max(res,max(0,L) + max(0,R) +root.val)
            return max(L,R,0) + root.val
        dfs(root)
        return res
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 max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }


    int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }


        int left = dfs(root.left);
        int right = dfs(root.right);
        
        //自我组合
        int tmp = left + right + root.val;
        //最大sum
        int sum =  Math.max(Math.max(left , right) +  root.val, root.val);
        max = Math.max(tmp, max);
        max = Math.max(sum, max);
        return sum;
    }
}

妙!