Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created August 4, 2016 18:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/5eab22189f0fd7a58aa4fbc56b725dd8 to your computer and use it in GitHub Desktop.
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
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