Binary Tree Maximum Path Sum

1package pkg5leetcode.blind75;2 3/*4 * Binary Tree Maximum Path Sum | LC 1245 * APPROACH: Post-order gain through node vs global max path.6 * COMPLEXITY: Time O(n), Space O(h)7 */8public class blind75_LC124BinaryTreeMaximumPathSum {9    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */10 11    static class TreeNode {12        int val;13        TreeNode left, right;14        TreeNode(int val) { this.val = val; }15    }16 17    static int best;18 19    static int maxPathSum(TreeNode root) {20        best = Integer.MIN_VALUE;21        gain(root);22        return best;23    }24 25    static int gain(TreeNode node) {26        if (node == null) return 0;27        int left = Math.max(0, gain(node.left));28        int right = Math.max(0, gain(node.right));29        best = Math.max(best, node.val + left + right);30        return node.val + Math.max(left, right);31    }32 33    public static void main(String[] args) {34        TreeNode root = new TreeNode(-10);35        root.left = new TreeNode(9);36        root.right = new TreeNode(20);37        root.right.left = new TreeNode(15);38        root.right.right = new TreeNode(7);39        check(maxPathSum(root) == 42, "case1");40        TreeNode r2 = new TreeNode(1); r2.left = new TreeNode(2); r2.right = new TreeNode(3);41        check(maxPathSum(r2) == 6, "case2");42        System.out.println("all tests passed");43    }44 45    static void check(boolean cond, String name) {46        if (!cond) throw new AssertionError("FAILED: " + name);47        System.out.println("  PASS " + name);48    }49}