Description

LeetCode 124

Given a non-empty 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 must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

Analysis

The main point of this problem is to consider the two conditions of one node. One node could be the root or included as a child.

If one node is seen as a root, then the result should be the node’s value, the result of the left child and the result of the right child. It should not be added to its parent’s result recursively.

Otherwise, the result should be the maximum of the node’s value, the node’s value plus the result of the left child and the node’s value plus the result of the right child. It is the node’s result when the function of its parent calls it.

The results of two conditions aren’t easy to be compared directly. A good way is to set a global variable to store and update the maximum result for every node.

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int res=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        int x=helper(root);
        res=Math.max(res,x);
        return res;
    }
    public int helper(TreeNode root)
    {
        if(root==null) return 0;
        int left=helper(root.left);
        int right=helper(root.right);
        int x=Math.max(Math.max(root.val,root.val+left),root.val+right);
        res=Math.max(res,x);
        res=Math.max(res,root.val+left+right);
        return x;
    }
}

Reference

[1] https://www.geeksforgeeks.org/find-maximum-path-sum-in-a-binary-tree/

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *