Created
August 4, 2016 18:53
-
-
Save jianminchen/5eab22189f0fd7a58aa4fbc56b725dd8 to your computer and use it in GitHub Desktop.
Leetcode Binary Tree Max Path Sum - creative way to write code - first try
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 _BinaryTreeMaximumValueEndByRoot | |
{ | |
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); | |
int crossRoot = 0; | |
getMaximumEndByRoot(n1, ref crossRoot); | |
return crossRoot; | |
} | |
/* | |
* 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); | |
int crossRoot = 0; | |
getMaximumEndByRoot(n1, ref crossRoot); | |
return crossRoot; | |
} | |
/* | |
* 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); | |
int crossRoot = 0; | |
getMaximumEndByRoot(n1, ref crossRoot); | |
return crossRoot; | |
} | |
/* | |
* Analyze the binary tree maximum value ended by root node problem. | |
* | |
* Add some analysis and reasoning here: | |
* The problem is to solve the path from any node of the tree to another node of the tree. | |
* | |
* | |
*/ | |
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 + ((left > 0) ? left : 0) + ((right > 0) ? right : 0); | |
maxCrossRoot = (value > maxCrossRoot)? value: maxCrossRoot; | |
// 3 values, get maximum one. | |
return Math.Max(root.val, Math.Max(root.val + left, root.val + right)); | |
} | |
private static int getMaximumEndByRoot_Basic(TreeNode root) | |
{ | |
if (root == null) | |
return 0; | |
int left = getMaximumEndByRoot_Basic(root.left); | |
int right = getMaximumEndByRoot_Basic(root.right); | |
// 3 values, get maximum one. | |
return Math.Max(root.val, Math.Max(root.val + left, root.val + right)); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment