树

#include<bits stdc="">
using namespace std;
vectorinOrder;
vectorpostOrder;
int n;
typedef struct node{
	int data;
	struct node* lchild;
	struct node* rchild;
}Node;
// 后序序列的起止下标，中序序列的起止下标
Node* create(int postPre,int postEnd,int inPre,int inEnd)
{
	if(postPre>postEnd) return NULL;
    // 建立根节点
	Node* root = (Node*)malloc(sizeof(Node));
	root->lchild=root->rchild=NULL;

	int data = postOrder[postEnd];
	root->data = data;
	int index;
	for(index=inPre;index<=inEnd;++index) { if(inOrder[index]==data) break; } // 递归建立左右子树 root->lchild=create(postPre,postPre+index-inPre-1,inPre,index-1);
	root->rchild=create(postPre+index-inPre,postEnd-1,index+1,inEnd);
	return root;
}
int main()
{
	cin>>n;
	int temp;
	for(int i=0;i<n>>temp;
		postOrder.push_back(temp);

	}
	for(int j=0;j<n>>temp;
		inOrder.push_back(temp);
	}
	Node* root = create(0,6,0,6);
	queue<node>q;
	q.push(root);
	while(!q.empty())
	{
		Node* p=q.front();
		q.pop();
		cout<data><<" ";="" if(p-="">lchild)
		   q.push(p->lchild);
		if(p->rchild)
		   q.push(p->rchild);
	}

	return 0;
}
</data></node></n></n></bits>

#include <bits/stdc++.h>

using namespace std;
//定义树节点
struct TreeNode{
    TreeNode* left;
    TreeNode* right;
    int val;
    TreeNode(int v){
        left=right=nullptr;
        val=v;
    }
};

int stoi_(string s){
    int ret = 0;
    for(int i=0;i<s.size();++i){
        ret = ret*10 + s[i]-'0';
    }
    return ret;
}
//从字符串建树
TreeNode* createTree(vector<string>& s,int& idx){
    if(s[idx]=="#"){
        ++idx;
        return nullptr;
    }

    TreeNode* root = new TreeNode(stoi_(s[idx++]));
    root->left = createTree(s,idx);
    root->right = createTree(s,idx);
    return root;

}

vector<string> split(string& s,char c){
    string tmp = "";
    vector<string>ret;
    for(int i=0;i<s.size();++i){
        if(s[i]==c){
            ret.push_back(tmp);
            tmp = "";

        }
        else{
            tmp+=s[i];

        }
    }
    if(!tmp.empty()){
        ret.push_back(tmp);
    }
    return ret;
}
void visit(TreeNode* root){
    if(root){
        cout<<root->val<<" ";
        visit(root->left);
        visit(root->right);
    }

}
void findPath(TreeNode* root,int target,vector<vector<int>>& ans,int& flag,vector<int>& tmp){
    if(!root) return;
    if(root->val==target){
        flag = 1;
        tmp.push_back(root->val);
        ans.push_back(tmp);
        return;
    }
    tmp.push_back(root->val);
    if(root->left){
        findPath(root->left,target,ans,flag,tmp);
                //回溯
        tmp.pop_back();
    }
    if(!flag && root->right){
        findPath(root->right,target,ans,flag,tmp);
                //回溯
        tmp.pop_back();
    }
}

int main()
{
    string s = "1 5 3 # # # 9 4 7 # 2 # # # 6 # #";
    vector<string> v = split(s,' ');
    int idx = 0;
    //for(int i=0;i<v.size();++i)
    //    cout<<v[i]<<" ";
    //cout<<endl;
    TreeNode* root = createTree(v,idx);
    //visit(root);
    vector<vector<int>>paths;
    vector<int>tmp;
    int flag = 0;
    int target = 2;
    findPath(root,target,paths,flag,tmp);
    for(int i=0;i<paths[0].size();++i){
        cout<<paths[0][i]<<" ";
    }
    return 0;
}