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

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts