Binary Tree Maximum Path Sum--LeetCode

忘是亡心i 2022-08-07 12:38 2阅读 0赞

# 题目： #

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   3

思路：刚开始思路理解错误，理解为从根节点到所有的叶子节点的所有路径中，最大的路径和。如果是这样，代码如下；

void helper_sum(BinTree* root,vector<int>& path,int& maxsum)
    {
    	if(root == NULL)
    		return ;
    	path.push_back(root->value);
    	if(root->left == NULL && root->right == NULL)
    	{
    		int tmp=0;
    		for(int i=0;i<path.size();i++)
    		{
    			tmp += path[i];
    			cout<<path[i]<<" ";
    		}
    		cout<<"tmp is "<<tmp<<endl; 
    		cout<<endl;
    		maxsum  = max(tmp,maxsum);
    	//	cout<<"tmp is "<<tmp<<endl; 
    		//return ;
    	}
    	
    	helper_sum(root->left,path,maxsum);
    	helper_sum(root->right,path,maxsum);
    	path.pop_back();
    }
    
    int MaxPathSum(BinTree* root)
    {
    	if(root == NULL)
    		return 0;
    	vector<int> path;
    	int maxsum=0;
    	helper_sum(root,path,maxsum);
    	return maxsum;
    }

求出所有的根节点到叶子接到的路径和，找到最大的即可。

如果按照题意要求，那么从任意一个节点开始，任意一个节点结束，那么可能会出现下面的情况，最大的路径不经过根节点，最大的路径经过根节点。

如果最大的路径不经过根节点，那么最大的路径要么在左子树中，要么在右子树中，如果经过根节点，那么左子树最大+右子树最大+根节点的值。

最终的结果是取三个之最。

这道题是求树的路径和的题目，不过和平常不同的是这里的路径不仅可以从根到某一个结点，而且路径可以从左子树某一个结点，然后到达右子树的结点，就像题目中所说的可以起始和终结于任何结点。在这里树没有被看成有向图，而是被当成无向图来寻找路径。因为这个路径的灵活性，我们需要对递归返回值进行一些调整，而不是通常的返回要求的结果。在这里，函数的返回值定义为以自己为根的一条从根到子结点的最长路径（这里路径就不是当成无向图了，必须往单方向走）。这个返回值是为了提供给它的父结点计算自身的最长路径用，而结点自身的最长路径（也就是可以从左到右那种）则只需计算然后更新即可。这样一来，一个结点自身的最长路径就是它的左子树返回值（如果大于0的话），加上右子树的返回值（如果大于0的话），再加上自己的值。而返回值则是自己的值加上左子树返回值，右子树返回值或者0（注意这里是“或者”，而不是“加上”，因为返回值只取一支的路径和）。在过程中求得当前最长路径时比较一下是不是目前最长的，如果是则更新。算法的本质还是一次树的遍历，所以复杂度是O(n)。而空间上仍然是栈大小O(logn)。代码如下：

/ 返回以root为根的最大和的一条单向路径 
    int MaxSum(BinTree* root,int& maxsum)
    {
        if(root == NULL)
         return 0;
        int maxleft= MaxSum(root->left,maxsum);
        int maxright = MaxSum(root->right,maxsum);
        int cur = root->value +max(maxright,0)+max(maxleft,0);
        maxsum = max(maxsum,cur);
        
        return root->value+max(maxright,max(maxleft,0));
        
    }
    
    int MaxPahtSum(BinTree* root)
    {
        if(root == NULL)
         return 0;
        int sum = root->value;
        MaxSum(root,sum);
        return sum;
    }