Comment

Huhu_Miao: 2024-10-31 18:08:14

#include<bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

void printVector(const std::vector<int> & vec){
	for(const int & elem : vec){
		std::cout << elem << ' ';
	}
	std::cout << '\n';
}

int find(const std::vector<int> & vec, int target){
	for(int i = 0 ; i < vec.size() ; i++){
		if (target == vec[i]){return i;}
	}
	throw std::logic_error("unexpected exception.");
}

class binaryTree;

struct node
{
	node* left;
	int val;
	node* right;
};

class binaryTree{
public:
	binaryTree():_root(new node{.left=nullptr, .val=0, .right=nullptr}){}
	void buildTree(const std::vector<int> & VLR , const std::vector<int> & LVR){
		//std::cerr << "building tree.." << std::endl;
		_root->val = VLR[0];
		if(VLR.size() == 1){return ;}
		int targetIndex_LVR = find(LVR,VLR[0]);
		if(targetIndex_LVR == LVR.size() - 1){
			std::vector<int> left_VLR(VLR.begin()+1,VLR.begin()+targetIndex_LVR+1);
			std::vector<int> left_LVR(LVR.begin(),LVR.begin()+targetIndex_LVR);
			binaryTree * left_tree = new binaryTree;
			left_tree->buildTree(left_VLR,left_LVR);
			_root->left = left_tree->_root;
			return;
		}
		if(targetIndex_LVR == 0){
			std::vector<int> right_VLR(VLR.begin()+1,VLR.end());
			std::vector<int> right_LVR(LVR.begin()+1,LVR.end());
			binaryTree * right_tree = new binaryTree;
			right_tree->buildTree(right_VLR,right_LVR);
			_root->right = right_tree->_root;
			return;
		}
		std::vector<int> left_VLR(VLR.begin()+1,VLR.begin()+targetIndex_LVR+1);
		std::vector<int> left_LVR(LVR.begin(),LVR.begin()+targetIndex_LVR);
		//printVector(left_VLR);printVector(left_LVR);
		std::vector<int> right_VLR(VLR.begin()+targetIndex_LVR+1,VLR.end());
		std::vector<int> right_LVR(LVR.begin()+targetIndex_LVR+1,LVR.end());
		//printVector(right_VLR);printVector(right_LVR);

		binaryTree * left_tree = new binaryTree;
		binaryTree * right_tree = new binaryTree;
		left_tree->buildTree(left_VLR,left_LVR);
		_root->left = left_tree->_root;
		right_tree->buildTree(right_VLR,right_LVR);
		_root->right = right_tree->_root;
	}
	~binaryTree(){}
	void traverse_LRV(){
		_traverse_LRV(_root);
	}

private:
	void _traverse_LRV(node * nodePtr){
		if(nodePtr){
			_traverse_LRV(nodePtr->left);
			_traverse_LRV(nodePtr->right);
			std::cout << nodePtr->val << ' ';
		}
	}
	node* _root;
};

void solve(){
	int size1,size2;
	std::cin >> size1;
	std::vector<int> VLR(size1);
	for(int & elem : VLR){
		std::cin >> elem;
	}
	std::cin >> size2;
	std::vector<int> LVR(size2);
	for(int & elem : LVR){
		std::cin >> elem;
	}

	binaryTree Tree;
	Tree.buildTree(VLR,LVR);
	Tree.traverse_LRV();
	std::cout << '\n';
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int T;
	std::cin>>T;

	while(T--){
		solve();
	}


	return 0;
}

RockyChen0205: 2023-11-10 17:10:10

#include<iostream>
#include<vector>
#define size0 10000
#define size1 10000
#define size2 10000
using namespace std;

int pre[size0];
int post[size1];
int mp[size2];
int preHead;
int postHead;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

TreeNode* build(int pl,int pr, int il,int ir){
	TreeNode* root = new TreeNode(pre[pl]);
	int k=mp[root->val];
	if(k>il) root->left=build(pl+1,k-il+pl,il,k-1);
	if(k<ir) root->right=build(k-il+pl+1,pr,k+1,ir);
	return root;
}
void postOrder(TreeNode* root,vector<int>& result){
	if(root==nullptr) return;
	postOrder(root->left,result);
	postOrder(root->right,result);
	result.push_back(root->val);
	return ;
}

int main(){
	int n;
	cin>>n;
	vector<vector<int>> result(n);
	for(int i=0;i<n;i++){
		cin>>preHead;
		for(int j=1;j<=preHead;j++){
			cin>>pre[j];
		}
		cin>>postHead;
		for(int x=1;x<=postHead;x++){
			cin>>post[x];
			mp[post[x]]=x;
		}
		TreeNode* root=build(1,preHead,1,postHead);
		postOrder(root,result[i]);
		
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<result[i].size();j++){
			cout<<result[i][j]<<' ';
		}
		cout<<endl;
	}
}

Edward: 2022-12-04 16:28:32

求教，此题一直ac不了，显示是runtime error或者 memory exceeded