Leetcode 124 Binary Tree Maximum Path Sum

Leetcode 124. Binary Tree Maximum Path Sum

  • Requirement:
    Get the maximum path with max sum, and the path should be with a highest tree node. 

    1
    2   3

  • DFS Logic: Design a function with returning the max left path, return like ~ max(left, right) + node.val, and
    during the process, we have check the max( res, left + node.val + right);
    the code will be as followed: 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
     public class Solution {
     	int maxValue; // res
     	public int maxPathSum(TreeNode root){
     		maxValue = Integer.MIN_VALUE;
     		maxPathDown(root);
     		return maxValue;
    }
    private int maxPathDown(TreeNode node){
    if(node == null) return 0;
    //get the left max path(only drilling down from the left/right node)
    int left = Math.max(0, maxPathDown(node.left));
    int right = Math.max(0, maxPathDown(node.right));
    maxValue = Math.max(left, right) + node.val;
    }
     }