Created
August 5, 2016 04:57
-
-
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,
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 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