二叉树中最大路径 保持父子 始末未知

#include<iostream>
using namespace std;
int ans,path[110],maxpath[110],k,start,ens,f,maxlen;
struct TreeNode{
    int data;
    TreeNode*left;
    TreeNode*right;
};
TreeNode* CreateTree(){
    int k;
    scanf("%d",&k);
    if(k==0)return nullptr;
    TreeNode*root=new TreeNode;
    root->data=k;
    root->left=CreateTree();
    root->right=CreateTree();
    return root;
}
void findPath(TreeNode*t,int f,int k,int &max){
    if(!t)return;
    path[k]=t->data;
    if(k==0){f=t->data;start=k;}//起点
    else if(f>0){f+=t->data;}
    else{f=t->data;start=k;}
    ens=k;
    if((f>max)||(f==max&&ens-start+1<maxlen)){
        max=f;
        for(int i=start;i<=ens;i++)
            maxpath[i-start]=path[i];
        maxlen=ens-start+1;
    }
    findPath(t->left,f,k+1,max);
    findPath(t->right,f,k+1,max);
}
int main(){
    TreeNode*root=CreateTree();
    ans=-1e8;
    findPath(root,f,k,ans);
    cout<<ans<<endl;
    for(int i=0;i<=ens-start;i++)cout<<maxpath[i]<<" ";
    return 0;
}

最右子式

//1858
#include<iostream>
#include<stack>
#include<vector>
#include<queue>
using namespace std;
//思路层次遍历各层最后一个点
int n;string str;
vector<char>ans;
struct TreeNode{
    char data;
    TreeNode*left;
    TreeNode*right;
};
TreeNode*Build(string str){
    stack<TreeNode*>stk;
    for(int i=0;i<str.size();i++){
        TreeNode*root=new TreeNode;
        root->data=str[i];
        if(str[i]>='a'&&str[i]<='z')root->left=root->right=nullptr;
        else{
            root->right=stk.top();stk.pop();
            root->left=stk.top();stk.pop();
        }
        stk.push(root);
    }
    return stk.top();
}
void bfs(TreeNode*root){
    queue<TreeNode*>q;
    if(!root)return;
    q.push(root);
    while(q.size()){
        int n=q.size();
        for(int i=0;i<n;i++){
            auto t=q.front();q.pop();
            if(t->left)q.push(t->left);
            if(t->right)q.push(t->right);
            if(i==n-1)ans.push_back(t->data);
        }
    }
}
int main(){
    cin>>n;
    while(n--){
        cin>>str;
        TreeNode*root=Build(str);
        ans.clear();//清空操作
        bfs(root);
        for(auto c:ans)cout<<c;
        cout<<endl;
    }
    return 0;
}

重建树

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=26;
char post[N];
char in[N];
struct TreeNode{
    char data;
    TreeNode*left;
    TreeNode*right;
};
int find(char*in,int n,char val){
    for(int i=0;i<n;i++)
        if(in[i]==val)return i;
    return -1;
}
void Pre(TreeNode*root){
    if(!root)return;
    cout<<root->data;
    Pre(root->left);
    Pre(root->right);
}
bool flag =false;
TreeNode*reBuild(char*post,char*in,int n){
    if(flag)return nullptr;
    if(n<=0)return nullptr;
    char rootval =post[n-1];
    TreeNode*root=new TreeNode;
    root->data=rootval;
    int k=find(in,n,rootval);
    if(k==-1){flag=true;return nullptr;}
    root->left=reBuild(&post[0],&in[0],k);
    root->right=reBuild(&post[k],&in[k+1],n-k-1);
    return root;
}
int  depth(TreeNode*root){
    if(!root)return -1;
    return max(depth(root->left),depth(root->right))+1;
}
int main(){
while(cin>>post>>in){
    int n1=string(post).size();
    int n2=string(in).size();
    TreeNode*root=reBuild(post,in,n1<=n2?n1:n2);
    if(flag){puts("INVALID");flag=false;continue;}
    cout<<depth(root)<<endl;
    Pre(root);
    cout<<endl;
}

return 0;
}