Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,1 / \ 2 3Return
6.Tags: tree, depth-first-search
10/10/2015 udpate
divide-and-conquer approach
o(n) solution, use a fancy recursion function, do two works together.
It returns the path sum starts from root node to nodes below,
res is the current maximum sum path
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int MININT = 0x8fffffff;
int maxPathSum(TreeNode* root) {
int res = MININT;
pathSum(root, res);
return res;
}
//return the max path sum that starts from root
//res is the maximum path sum in this tree
int pathSum(TreeNode * root, int& res){
if(root == nullptr) return -1;
int left = pathSum(root->left, res);
int right = pathSum(root->right, res);
int tmp = root->val;
tmp = left > 0? tmp + left: tmp;
tmp = right > 0? tmp + right: tmp;
res = max(res, tmp);
return max(max(left, right), 0) + root->val;
}
};
O(nlogn) solution, not quite efficient, time limit excced.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int MININT = 0x80000000;
int maxPathSum(TreeNode* root) {
if(root == nullptr){
return MININT;
}
int left = maxPathSum(root->left);
int right = maxPathSum(root->right);
int leftPath = maxToRootSum(root->left);
int rightPath = maxToRootSum(root->right);
int tmp = root->val;
tmp = leftPath > 0? tmp + leftPath: tmp;
tmp = rightPath > 0? tmp + rightPath: tmp;
return max(left, max(right, tmp));
}
int maxToRootSum(TreeNode * root){
if(root == nullptr) return -1;
int left = maxToRootSum(root->left);
int right = maxToRootSum(root->right);
int tmp = root->val;
tmp = max(left, right) > 0? tmp + max(left, right): tmp;
return tmp;
}
};
Tag里没写divide-and-conquer. 但我还是先想到了一个分治的算法.
这道题让我想起数据结构书上,第一章的那个作为引子的,最大子序列问题.我想着把这个树近似成一个多叉数组来处理,这里化用了原书里的第三个分而治之的算法,时间复杂度O(nlogn).但是竟然没让我过!说是超时.我还在想O(n)的算法.或许应该化用书中第四个算法.记得那个算法是O(n)的复杂度.
版本一:O(nlogn),分治算法,超时
需要注意,max只接受两两参数的比较.如果多参数比较的话,需要嵌套max函数.
C++:
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
/**
* divide and conque
**/
int maxPathSum(TreeNode *root) {
int leftSum, rightSum, leftAdjacentSum, rightAdjacentSum;
bool isLeftSet = false;
bool isRightSet = false;
//leaf node
if(root->left == NULL && root->right == NULL){
return root->val;
}
else{
if(root->left != NULL){
isLeftSet = true;
leftSum = maxPathSum(root->left);
leftAdjacentSum = maxAdjacentPathSum(root->left);
}
if(root->right != NULL){
isRightSet = true;
rightSum = maxPathSum(root->right);
rightAdjacentSum = maxAdjacentPathSum(root->right);
}
//due to the if condition in line 21, either isLeftSet or isRightSet should be true.
if(isRightSet == false){
//isLeftSet is true
return max(leftSum, max(leftAdjacentSum, 0) + root->val);
}
else if(isLeftSet == false){
//isRightSet is true
return max(rightSum, max(rightAdjacentSum, 0) + root->val);
}
else{
//both isRightSet and isLeftSet is true
//if either the rightAjacentSum or the leftAjacentSum is smaller than 0, discard it.
return max(max(leftSum, rightSum), max(leftAdjacentSum, 0) + max(rightAdjacentSum, 0) + root->val);
}
}
}
int maxAdjacentPathSum(TreeNode *root){
int maxLeft, maxRight;
bool isLeftSet = false;
bool isRightSet = true;
if(root->left == NULL && root->right == NULL){
return root->val;
}
if(root->left != NULL){
maxLeft = maxAdjacentPathSum(root->left);
isLeftSet = true;
}
if(root->right != NULL){
maxRight = maxAdjacentPathSum(root->right);
isRightSet = true;
}
if(isRightSet == false){
return max(maxLeft, 0) + root->val;
}
else if(isLeftSet == false){
return max(maxRight, 0) + root->val;
}
else{
return max(max(maxRight, maxLeft), 0) + root->val;
}
}
};
一月二十二号晚更新：
找到了时间复杂度为O(n)的办法。其实版本一已经很接近O(n)了，只是我的递归没有写好，maxAdjacentPathSum是多余的，它的工作完全可以合并在maxPathSum里。从结构上也不难发现，它的函数结构和maxPathSum有惊人的相似。
实际上，maxAdjacentSum所需要的信息在maxPathSum的递归时已经得到了。正如数据结构书的第一章介绍递归时所讲，“永远不要把同一个东西计算两次。”
我只是机械性地把两个函数合并在了一起。虽然AC了，但执行效率依旧比第一名有一些差距。不知有没有更有效率的方法？或者用循环来代替递归？
版本二：简化后的分治算法，AC
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class ReturnValue{
public:
int maxPathSum;
int maxAdjacentSum;
ReturnValue(int x, int y):maxPathSum(x), maxAdjacentSum(y){}
};
class Solution {
public:
/**
* divide and conquer
**/
int maxPathSum(TreeNode *root){
return _maxPathSum(root)->maxPathSum;
}
ReturnValue * _maxPathSum(TreeNode *root) {
int leftSum, rightSum, leftAdjacentSum, rightAdjacentSum;
bool isLeftSet = false;
bool isRightSet = false;
ReturnValue * p;
//leaf node
if(root->left == NULL && root->right == NULL){
return new ReturnValue(root->val, root->val);
}
else{
if(root->left != NULL){
isLeftSet = true;
p = _maxPathSum(root->left);
leftSum = p->maxPathSum;
leftAdjacentSum = p->maxAdjacentSum;
}
if(root->right != NULL){
isRightSet = true;
p = _maxPathSum(root->right);
rightSum = p->maxPathSum;
rightAdjacentSum = p->maxAdjacentSum;
}
//due to the if condition in line 21, either isLeftSet or isRightSet should be true.
if(isRightSet == false){
//isLeftSet is true
int thisMaxPathSum = max(leftSum, max(leftAdjacentSum, 0) + root->val);
int thisMaxAdjacentSum = max(leftAdjacentSum, 0) + root->val;
return new ReturnValue(thisMaxPathSum, thisMaxAdjacentSum);
}
else if(isLeftSet == false){
//isRightSet is true
int thisMaxPathSum = max(rightSum, max(rightAdjacentSum, 0) + root->val);
int thisMaxAdjacentSum = max(rightAdjacentSum, 0) + root->val;
return new ReturnValue(thisMaxPathSum, thisMaxAdjacentSum);
}
else{
//both isRightSet and isLeftSet is true
//if either the rightAjacentSum or the leftAjacentSum is smaller than 0, discard it.
int thisMaxPathSum = max(max(leftSum, rightSum), max(leftAdjacentSum, 0) + max(rightAdjacentSum, 0) + root->val);
int thisMaxAdjacentSum = max(max(rightAdjacentSum, leftAdjacentSum), 0) + root->val;
return new ReturnValue(thisMaxPathSum, thisMaxAdjacentSum);
}
}
}
};
