http://lixinzhang.github.io/itint5-mian-shi-ti-zong-jie.html
https://github.com/AnnieKim/ITint5/blob/master/013_%E6%A0%91%E4%B8%AD%E6%9C%80%E5%A4%A7%E8%B7%AF%E5%BE%84%E5%92%8C.cpp
扩展:此题算法也可用来解决另一个非常常见的面试题“树的直径”(求树中任意两结点路径的长度的最大值)。
可以认为树中每个结点的val值为1,那么求最长路径相当于求路径值最大的路径。
Solution: LeetCode中Binary Tree Maximum Path Sum的扩展,这里是树,而非二叉树。
*/
/*
树结点的定义(请不要在代码中定义该类型)
struct TreeNode {
int val;
vector<TreeNode*> children; //该结点的儿子结点
};
*/
int maxTreePathSumRe(TreeNode *root, int &res) {
if (!root) return res;
int N = root->children.size();
int first = 0, second = 0;
for (int i = 0; i < N; ++i)
{
int sum = maxTreePathSumRe(root->children[i], res);
if (sum > first) {
second = first;
first = sum;
} else if (sum > second) {
second = sum;
}
}
int maximum = root->val;
maximum = max(maximum, root->val + first);
res = max(res, maximum);
res = max(res, root->val + first + second);
return maximum;
}
int maxTreePathSum(TreeNode *root) {
int res = 0;
maxTreePathSumRe(root, res);
return res;
}
https://github.com/ralphite/ITint5-Answers-Java/blob/master/%E6%A0%91%E4%B8%AD%E6%9C%80%E5%A4%A7%E8%B7%AF%E5%BE%84%E5%92%8C.java
public int maxTreePathSum(TreeNode root) {
HashMap<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
calc(root, map);
IntHolder max = new IntHolder();
max.val = 0;
calc2(root, map, max);
return max.val;
}
private static void calc2(TreeNode root, HashMap<TreeNode, Integer> map,
IntHolder max) {
if(root == null) return;
if(root.children == null || root.children.size() == 0) {
max.val = max.val < root.val ? root.val : max.val;
}
//find biggest 2
int m1 = 0;
int m2 = 0;
for(TreeNode n : root.children) {
int v = map.get(n);
if (v > m2) {
m2 = v;
}
if(m1 < m2) {
int t = m1;
m1 = m2;
m2 = t;
}
}
if(max.val < m1 + m2 + root.val) {
max.val = m1 + m2 + root.val;
}
for(TreeNode n : root.children) {
calc2(n, map, max);
}
}
private static void calc(TreeNode root, HashMap<TreeNode, Integer> map) {
if(root == null) return;
if(root.children == null || root.children.size() == 0) {
map.put(root, root.val);
return;
}
int max = 0;
for(TreeNode n : root.children) {
calc(n, map);
int v = map.get(n);
max = v > max? v : max;
}
map.put(root, root.val + max);
return;
}
private static class IntHolder {
int val;
}
[itint5]树中最大路径和 - 阿牧遥 - 博客园
要注意,一是空路径也可以,所以最小是0。然后要时刻注意路径顶多有两条子路径+根节点组成,所以更新全局最值时和返回上一级的值要注意分清。
https://github.com/jianminchen/TreeMaxPathSum/blob/master/Program.cs
public static int maxTreePathSumRe(TreeNode root, ref int res) {
if (root == null) return res;
int N = (root.children==null)?0:root.children.Length;
// 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
// yeah, through the debug, she knows the idea.
int first = 0, second = 0;
for (int i = 0; i < N; ++i)
{
TreeNode[] a = root.children;
TreeNode b = (TreeNode)a[i];
int sum = maxTreePathSumRe(b, ref res);
if (sum > first) {
second = first;
first = sum;
} else if (sum > second) {
second = sum;
}
}
int maximum = root.val;
maximum = max(maximum, root.val + first);
res = max(res, maximum);
res = max(res, root.val + first + second);
return maximum;
}
Read full article from [itint5]树中最大路径和 - 阿牧遥 - 博客园
给定一棵树的根结点,树中每个结点都包含一个整数值val。我们知道树中任意2个结点之间都存在唯一的一条路径,路径值为路径上所有结点值之和。请计算最大的路径值(允许路径为空)。
-10 / | \ 2 3 4 / \ 5 -1 / 6 / -1 最大的路径值为13,相应的路径为5到6之间的路径。
应该算是路径和最大那题的更普遍情况,需要注意的是三种情况,res=max(左+右+root,max(左,右),root)
另外就是不要指望通过返回值拿到最后的结果,函数返回值仍然为以该节点为根的路径之和最大值,max(左,右) .
当然,这道题里的左右为children里面的最大值和次大值。
/* 树结点的定义(请不要在代码中定义该类型) struct TreeNode { int val; vector<TreeNode*> children; //该结点的儿子结点 }; */ const int INT_MIN = -9999999; int _search(TreeNode * root, int & curmax); int updateMax(vector<int> &children, int root, int & curmax); int maxTreePathSum(TreeNode *root) { if(root == NULL) return 0; int curmax = 0; _search(root, curmax); return curmax; } int _search(TreeNode * root, int & curmax){ if(root == NULL) return 0; vector<int> children; for(int i=0; i<root->children.size(); i++){ children.push_back(_search(root->children[i], curmax)); } int childmax = updateMax(children, root->val, curmax); return root->val + max(childmax, 0); } int updateMax(vector<int> &children, int root, int & curmax){ int max1 = INT_MIN, max2 = INT_MIN; int max_idx = 0; for(int i=0; i<children.size(); i++){ if(max1 <= children[i]){ max1 = children[i]; max_idx = i; } } for(int i=0; i<children.size(); i++){ if(max_idx == i) continue; max2 = max(max2, children[i]); } if(max2 >= 0){ curmax = max(curmax, root + max1 + max2); }else if(max1 >= 0){ curmax = max(curmax, root + max1); }else{ curmax = max(curmax, root); } return max1; }
扩展:此题算法也可用来解决另一个非常常见的面试题“树的直径”(求树中任意两结点路径的长度的最大值)。
可以认为树中每个结点的val值为1,那么求最长路径相当于求路径值最大的路径。
Solution: LeetCode中Binary Tree Maximum Path Sum的扩展,这里是树,而非二叉树。
*/
/*
树结点的定义(请不要在代码中定义该类型)
struct TreeNode {
int val;
vector<TreeNode*> children; //该结点的儿子结点
};
*/
int maxTreePathSumRe(TreeNode *root, int &res) {
if (!root) return res;
int N = root->children.size();
int first = 0, second = 0;
for (int i = 0; i < N; ++i)
{
int sum = maxTreePathSumRe(root->children[i], res);
if (sum > first) {
second = first;
first = sum;
} else if (sum > second) {
second = sum;
}
}
int maximum = root->val;
maximum = max(maximum, root->val + first);
res = max(res, maximum);
res = max(res, root->val + first + second);
return maximum;
}
int maxTreePathSum(TreeNode *root) {
int res = 0;
maxTreePathSumRe(root, res);
return res;
}
https://github.com/ralphite/ITint5-Answers-Java/blob/master/%E6%A0%91%E4%B8%AD%E6%9C%80%E5%A4%A7%E8%B7%AF%E5%BE%84%E5%92%8C.java
public int maxTreePathSum(TreeNode root) {
HashMap<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
calc(root, map);
IntHolder max = new IntHolder();
max.val = 0;
calc2(root, map, max);
return max.val;
}
private static void calc2(TreeNode root, HashMap<TreeNode, Integer> map,
IntHolder max) {
if(root == null) return;
if(root.children == null || root.children.size() == 0) {
max.val = max.val < root.val ? root.val : max.val;
}
//find biggest 2
int m1 = 0;
int m2 = 0;
for(TreeNode n : root.children) {
int v = map.get(n);
if (v > m2) {
m2 = v;
}
if(m1 < m2) {
int t = m1;
m1 = m2;
m2 = t;
}
}
if(max.val < m1 + m2 + root.val) {
max.val = m1 + m2 + root.val;
}
for(TreeNode n : root.children) {
calc2(n, map, max);
}
}
private static void calc(TreeNode root, HashMap<TreeNode, Integer> map) {
if(root == null) return;
if(root.children == null || root.children.size() == 0) {
map.put(root, root.val);
return;
}
int max = 0;
for(TreeNode n : root.children) {
calc(n, map);
int v = map.get(n);
max = v > max? v : max;
}
map.put(root, root.val + max);
return;
}
private static class IntHolder {
int val;
}
[itint5]树中最大路径和 - 阿牧遥 - 博客园
要注意,一是空路径也可以,所以最小是0。然后要时刻注意路径顶多有两条子路径+根节点组成,所以更新全局最值时和返回上一级的值要注意分清。
public static int maxTreePathSumRe(TreeNode root, ref int res) {
if (root == null) return res;
int N = (root.children==null)?0:root.children.Length;
// 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
// yeah, through the debug, she knows the idea.
int first = 0, second = 0;
for (int i = 0; i < N; ++i)
{
TreeNode[] a = root.children;
TreeNode b = (TreeNode)a[i];
int sum = maxTreePathSumRe(b, ref res);
if (sum > first) {
second = first;
first = sum;
} else if (sum > second) {
second = sum;
}
}
int maximum = root.val;
maximum = max(maximum, root.val + first);
res = max(res, maximum);
res = max(res, root.val + first + second);
return maximum;
}
Read full article from [itint5]树中最大路径和 - 阿牧遥 - 博客园