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.

  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:

   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;
  }
   }