Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example:
Given the below binary tree,

       1
      / \
     2   3
Return 6.

When meet negative node, compare and cut.

    private int res;

    private int helper(TreeNode root) {
        if(root == null) return 0;

        int left = helper(root.left), right = helper(root.right);

        if(left < 0) {res = Math.max(left, res); left = 0;}

        if(right < 0) {res = Math.max(right, res); right = 0;}

        res = Math.max(left + right + root.val, res);

        return Math.max(left, right) + root.val;
    }

    public int maxPathSum(TreeNode root) {
        if(root == null) return 0;

        res = root.val;

        helper(root);

        return res;
    }

results matching ""

    No results matching ""