今�Hの国の呵呵君: [Algorithm]Get Path with Max Sum in Binary Tree

今�Hの国の呵呵君: [Algorithm]Get Path with Max Sum in Binary Tree

[Algorithm]Get Path with Max Sum in Binary Tree

是Binary Tree Maximum Path Sum的变形，这次是要把得到path而不是单纯的sum，解法也是类似的，只不过递归的时候return path，当在一个节点的时候，先得到左子树和右子树中最大的path，算出左边和右边的和，然后根据左边右边和自己的和判断是否需要更新最大值。然后return左边还是右边的策略和maximum path sum是一样的。T(N) = 2T(N/2) + O(N)，O(N)是每次要根据path来算出sum，根据master therom，时间复杂度为O(N log N)，代码如下：

Read full article from 今�Hの国の呵呵君: [Algorithm]Get Path with Max Sum in Binary Tree