Massive Algorithms: [itint5]树中最大路径和 - 阿牧遥

http://lixinzhang.github.io/itint5-mian-shi-ti-zong-jie.html

给定一棵树的根结点，树中每个结点都包含一个整数值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;
}

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。然后要时刻注意路径顶多有两条子路径+根节点组成，所以更新全局最值时和返回上一级的值要注意分清。

int maxPathHelper(TreeNode *root, int &max) {

    if (root == NULL) {

        return 0;

    }

    int root_val = root->val; // root it self

    int max1 = 0;

    int max2 = 0;

    for (int i = 0; i < root->children.size(); i++) {

        int max_sub = maxPathHelper(root->children[i], max);

        if (max_sub > max1) {

            max2 = max1;

            max1 = max_sub;

        } else if (max_sub > max2) {

            max2 = max_sub;

        }

    }

    int local_max = root_val;

    int tmp = root_val + max1;

    if (tmp > local_max) local_max = tmp;

    if (local_max > max) max = local_max;

    tmp = root_val + max1 + max2;

    if (tmp > max) max = tmp;

    return local_max;

}

int maxTreePathSum(TreeNode *root) {

    int max = 0;

    maxPathHelper(root, max);

    return max;

}

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]树中最大路径和 - 阿牧遥 - 博客园

[itint5]树中最大路径和 - 阿牧遥 - 博客园

Labels

Popular Posts