Created
May 31, 2016 22:20
-
-
Save jianminchen/432bdb1af38a1ec6f4a0741420891ebf to your computer and use it in GitHub Desktop.
Leetcode 124 - Binary tree maximum path sum - practice, pass online judge
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace _124BinaryTreeMaximumPathSum_JuliaWriteByHerself | |
{ | |
public class TreeNode | |
{ | |
public int val; | |
public TreeNode left; | |
public TreeNode right; | |
public TreeNode(int x) { val = x; } | |
} | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
int result = testCase_1(); | |
int result2 = testCase_2(); | |
int result3 = testCase_3(); | |
} | |
/* | |
* maximum value is ended by root value | |
*/ | |
public static int testCase_1() | |
{ | |
TreeNode n1 = new TreeNode(3); | |
n1.left = new TreeNode(2); | |
n1.left.left = new TreeNode(1); | |
n1.left.right = new TreeNode(3); | |
n1.right = new TreeNode(-1); | |
n1.right.left = new TreeNode(-2); | |
n1.right.right = new TreeNode(-2); | |
return maximumPathSum(n1); | |
} | |
/* | |
* maximum value is in subtree somewhere | |
*/ | |
public static int testCase_2() | |
{ | |
TreeNode n1 = new TreeNode(-3); | |
n1.left = new TreeNode(2); | |
n1.left.left = new TreeNode(1); | |
n1.left.right = new TreeNode(3); | |
n1.right = new TreeNode(-1); | |
n1.right.left = new TreeNode(-2); | |
n1.right.right = new TreeNode(-2); | |
return maximumPathSum(n1); | |
} | |
/* | |
* Test case: | |
* 9 6 -3 null null -6 2 null null -6 2 null null 2 null -6 -6 null null null null | |
* | |
* Maximum path is 6 9 -3 2 2 | |
*/ | |
public static int testCase_3() | |
{ | |
TreeNode n1 = new TreeNode(9); | |
n1.left = new TreeNode(6); | |
n1.right = new TreeNode(-3); | |
n1.right.left = new TreeNode(-6); | |
n1.right.right = new TreeNode(2); | |
n1.right.right.left = new TreeNode(2); | |
n1.right.right.left.left = new TreeNode(-6); | |
n1.right.right.left.right = new TreeNode(-6); | |
return maximumPathSum(n1); | |
} | |
/* | |
* pass online judge | |
* | |
* | |
*/ | |
public static int maximumPathSum(TreeNode root) | |
{ | |
if (root == null) | |
return 0; | |
int maxCrossRoot = Int32.MinValue; | |
int maxEndRoot = getMaximumEndByRoot(root, ref maxCrossRoot); | |
return Math.Max(maxEndRoot, maxCrossRoot); | |
} | |
/* | |
* Analyze the binary tree maximum path sum problem. | |
* | |
* Maximum path - | |
* Can be analyzed by two variable | |
* - Maximum value ended by root node | |
* - Maximum value cross by root node | |
* | |
*/ | |
private static int getMaximumEndByRoot(TreeNode root, ref int maxCrossRoot) | |
{ | |
if (root == null) | |
return 0; | |
int left = getMaximumEndByRoot(root.left, ref maxCrossRoot); | |
int right = getMaximumEndByRoot(root.right, ref maxCrossRoot); | |
int value = root.val; | |
if (left > 0) | |
value += left; | |
if (right > 0) | |
value += right; | |
maxCrossRoot = value > maxCrossRoot ? value : maxCrossRoot; | |
int maxValue = Math.Max(root.val + left, root.val + right); | |
return Math.Max(root.val, maxValue); // 3 values, get maximum one. | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment