Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created August 5, 2016 04:57
Show Gist options
  • Save jianminchen/3b2c8e0e84e52cbca2a7ec435b29a2e4 to your computer and use it in GitHub Desktop.
Save jianminchen/3b2c8e0e84e52cbca2a7ec435b29a2e4 to your computer and use it in GitHub Desktop.
Maximum Path Sum of Tree - 3rd writing, using Array.Max() on line 124, line 98 use array instead of 2 int variables,
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace TreeMaximumPathSum
{
class TreeNode
{
public int val;
public TreeNode[] children;
public TreeNode(int x)
{
val = x;
children = null;
}
};
class Program
{
static void Main(string[] args)
{
/*
* Test case:
*
-10
/ | \
2 3 4
/ \
5 -1
/
6
/
-1
* Maximum path sum: 5-> 3-> -1-> 6 , result is 13
*/
TreeNode n1 = new TreeNode(-10);
n1.children = new TreeNode[3];
n1.children[0] = new TreeNode(2);
n1.children[1] = new TreeNode(3);
n1.children[2] = new TreeNode(4);
TreeNode l2 = n1.children[1];
l2.children = new TreeNode[2];
l2.children[0] = new TreeNode(5);
l2.children[1] = new TreeNode(-1);
TreeNode l3 = l2.children[1];
l3.children = new TreeNode[1];
l3.children[0] = new TreeNode(6);
l3.children[0].children = new TreeNode[1];
l3.children[0].children[0] = new TreeNode(-1);
int result = maxTreePathSum(n1);
}
/*
Augst 4, 2016
*
题目: 树中最大路径和
难度: Easy
链接: http://www.itint5.com/oj/#13
问题:
给定一棵树的根结点,树中每个结点都包含一个整数值val。
我们知道树中任意2个结点之间都存在唯一的一条路径,路径值为路径上所有结点值之和。
请计算最大的路径值(允许路径为空)。
样例:
-10
/ | \
2 3 4
/ \
5 -1
/
6
/
-1
最大的路径值为13,相应的路径为5到6之间的路径。
扩展:此题算法也可用来解决另一个非常常见的面试题“树的直径”(求树中任意两结点路径的长度的最大值)。
可以认为树中每个结点的val值为1,那么求最长路径相当于求路径值最大的路径。
Solution: LeetCode 124 中Binary Tree Maximum Path Sum的扩展,这里是树,而非二叉树。
* julia added comment: need to find maximum path through the root node,
so, multiple children, only keep first two most biggest pathes.
For the test case, root.val = -10, there are 3 children, each has maximum path length through the root node: 2, 8, 4
so, the consideration is first 2 largest path length, 8 and 4.
-10 + 8 +4
*/
public static int maxSumEndByRoot(TreeNode root, ref int maxSumCrossRoot)
{
if (root == null) return maxSumCrossRoot;
int N = (root.children == null) ? 0 : root.children.Length;
int[] top2 = new int[2];
for (int i = 0; i < N; ++i)
{
TreeNode[] arr = root.children;
TreeNode runner = (TreeNode)arr[i];
int sum = maxSumEndByRoot(runner, ref maxSumCrossRoot);
if (sum > top2[0])
{
top2[1] = top2[0];
top2[0] = sum;
}
else if (sum > top2[1])
{
top2[1] = sum;
}
}
// either root value,
// maximum path + root value,
// or maximum path + second maximum path + root value
int rVal = root.val;
int[] sumArr = { rVal, rVal + top2[0], rVal + top2.Sum()};
maxSumCrossRoot = max(maxSumCrossRoot, sumArr.Max());
return max(sumArr[0], sumArr[1]);
}
public static int maxTreePathSum(TreeNode root)
{
int res = 0;
maxSumEndByRoot(root, ref res);
return res;
}
public static int max(int a, int b)
{
return Math.Max(a, b);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment