BinaryPathSum
这道题目思路是瞿神提出的，瞿神能力确实很强，大一下，没有OI经历，算法已经非常出色了，小弟确实佩服，想当年小弟还在纠结于高数C++。。。
可见瞿神确实是付出了超出常人几倍甚至几十倍的时间，算法数据结构似乎很多方面比我还强。。。。
这道题目是Leetcode一道挺难的题目，找BT里面最长的path，任意两个点的，C(n,2)里面找，一个DP，后序顺序推进，保证孩子都计算出了，我的代码有点冗长，但是最后还是TLE了，具体原因不明，
后来发现没有记忆花存储，递归了，改了还是TLE。
// LeetCodeLast50.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <map>
#include <stack>
#include <queue>
using namespace std;
class Solution {
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
public:
TreeNode* root;
int dp[10000];
map<TreeNode*, int> nodemap;
int maxPathSum(TreeNode *root) {
if(root==NULL) return 0;
LevelOrder(root);
stack<TreeNode* > S;
S.push(root);
TreeNode* p,*pre=NULL;
while(!S.empty())
{
p=S.top();
if( (p->left==NULL && p->right==NULL) || (pre!=NULL &&(pre==p->left || pre==p->right)))
{
d(p);
S.pop();
pre=p;
}
else
{
if(p->right)
S.push(p->right);
if(p->left)
S.push(p->left);
}
}
map<TreeNode*, int> ::iterator it=nodemap.begin();
int max=-1000;
/*
if(dp[it->second]==dp[nodemap[it->first->left]]+it->first->val)
max=dp[it->second]+dp[nodemap[it->first->right]];
if(dp[it->second]==dp[nodemap[it->first->right]]+it->first->val)
{
if(max<dp[it->second]+dp[nodemap[it->first->left]])
max=dp[it->second]+dp[nodemap[it->first->left]];
}*/
for(;it!=nodemap.end();it++)
{
/*
if(it->first->left!=NULL && dp[it->second]==dp[nodemap[it->first->left]]+it->first->val)
{
if(it->first->right!=NULL &&max<dp[it->second]+dp[nodemap[it->first->right]])
max=dp[it->second]+dp[nodemap[it->first->right]];
else if(it->first->right==NULL)
{
if(max<dp[it->second])
max=dp[it->second];
}
}
if(it->first->right!=NULL && dp[it->second]==dp[nodemap[it->first->right]]+it->first->val)
{
if(it->first->left!=NULL &&max<dp[it->second]+dp[nodemap[it->first->left]])
max=dp[it->second]+dp[nodemap[it->first->left]];
else if(it->first->left==NULL)
{
if(max<dp[it->second])
max=dp[it->second];
}
}
if(it->first->left==NULL && it->first->right==NULL)
{
if(max<dp[it->second])
max=dp[it->second];
}
else if(it->first->left!=NULL && it->first->right==NULL)
{
if(max<dp[it->second])
max=dp[it->second];
}
else if(it->first->left==NULL && it->first->right!=NULL)
{
if(max<dp[it->second])
max=dp[it->second];
}*/
if(it->first->left!=NULL && it->first->right!=NULL)
{
if(dp[it->second]==dp[nodemap[it->first->left]]+it->first->val && max<dp[it->second]+dp[nodemap[it->first->right]])
max=dp[it->second]+dp[nodemap[it->first->right]];
else if(dp[it->second]==dp[nodemap[it->first->right]]+it->first->val && max<dp[it->second]+dp[nodemap[it->first->left]])
max=dp[it->second]+dp[nodemap[it->first->left]];
else
{
if(max<dp[it->second])
max=dp[it->second];
}
}
else
{
if(max<dp[it->second])
max=dp[it->second];
}
}
return max;
}
void LevelOrder(TreeNode* root)
{
queue<TreeNode* > Q;
Q.push(root);
int i=0;
while(!Q.empty())
{
TreeNode* p=Q.front();
nodemap[p]=i;
i++;
Q.pop();
if(p->left!=NULL)
Q.push(p->left);
if(p->right!=NULL)
Q.push(p->right);
}
memset(dp,0,sizeof(int)*i);
}
int d(TreeNode*p)
{
//if(!node[i])return dp[i]=0;
//int l=node[i].l,r=node[i].r;
int x;
if((x=dp[nodemap[p]])!=0) return x;
int lefti,righti,i=nodemap[p];
if(p->left)
{
lefti=nodemap[p->left];
dp[lefti]=d(p->left);
}
if(p->right)
{
righti=nodemap[p->right];
dp[righti]=d(p->right);
}
//if(node[l])dp[l]=d(l);
//if(node[r])dp[r]=d(r);
if(p->left && p->right)
return dp[i]=max(max(dp[lefti],dp[righti]),0)+p->val;
else if(p->left && p->right==NULL)
return dp[i]=max(dp[lefti],0)+p->val;
else if(p->left==NULL && p->right)
return dp[i]=max(dp[righti],0)+p->val;
else
return dp[i]=p->val;
}
int Max(int a, int b, int c, int d)
{
int max=a;
if(max<b) max=b;
if(max<c) max=c;
if(max<d) max=d;
return max;
}
void Create(TreeNode* & root)
{
int data;
cin>>data;
if(data == -1) root=NULL;
else
{
root=new TreeNode(data);
Create(root->left);
Create(root->right);
}
}
void CreateLevelOrder(TreeNode* &root)
{
queue<TreeNode*> Q;
int data;
cin>>data;
if(data==-1)
{
root=NULL;
return;
}
else
root=new TreeNode(data);
Q.push(root);
while(!Q.empty())
{
TreeNode* p=Q.front();
Q.pop();
cin>>data;
if(data==-1)
p->left=NULL;
else
p->left=new TreeNode(data),Q.push(p->left);
cin>>data;
if(data==-1)
p->right=NULL;
else
p->right=new TreeNode(data),Q.push(p->right);
}
}
};
int _tmain(int argc, _TCHAR* argv[])
{
freopen("in.txt","r",stdin);
Solution S;
S.Create(S.root);
cout<<endl<<S.maxPathSum(S.root)<<endl;
return 0;
}
后来还是改成了记忆化搜索，用瞿神的代码基础上，修改成leetcode的接口AC了
#include <unordered_map>
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
unordered_map<TreeNode*, int> nodemap;
TreeNode *root;
int ans=-0x3ffffff,cnt=0;
Solution():root(NULL)
{
}
int Create(TreeNode*& root)
{
int data,x;
cin>>data;
if(data == -1){
root=NULL;
return 0;
}
else
{
if(root!=NULL)
root->val=data;
else
root=new TreeNode(data);
//root->left=new TreeNode(0);
//root->right=new TreeNode(0);
Create(root->left);
Create(root->right);
//x=max(0,max(Create(root->left),Create(root->right)))+root->val;
//nodemap[root]=x;
}
}
int PreOrder(TreeNode* root)
{
if(root)
{
//cout<<root->val<<" ";
if(nodemap.find(root)!=nodemap.end()) return nodemap[root];
int x;
x=max(0,max(PreOrder(root->left),PreOrder(root->right)))+root->val;
nodemap[root]=x;
return x;
}
else
return 0;
}
int get_max(TreeNode *x)
{
if(!x)return 0;
int tmp=nodemap[x];
if(x->left&&x->right)
{
if(tmp==nodemap[x->left]+x->val&&nodemap[x->right]>0)return tmp+nodemap[x->right];
if(tmp==nodemap[x->right]+x->val&&nodemap[x->left]>0)return tmp+nodemap[x->left];
}
return tmp;
}
int maxPathSum(TreeNode *x)
{
if(!cnt)PreOrder(x),cnt++;
if(!x)return 0;
if(x->left)ans=max(ans,maxPathSum(x->left));
if(x->right)ans=max(ans,maxPathSum(x->right));
ans=max(ans,get_max(x));
return ans;
}
};