牛客 -------- 合并二叉树

合并二叉树

        

1.构建树

• ①通过给出的信息得知有多少个节点，开辟好空间
• ②因为节点的信息是层序遍历的结果，所以有规律可循
• ③对树中的节点建立联系

2.合并树 (递归)

3.层序遍历树

#include
#include
#include
 
using namespace std;
 
struct Node {  //节点定义
	Node* left; 
	Node* right; 
	int value; 
 
	Node() 
		:left(nullptr),right(nullptr),value(0) 
	{} 
};
 
Node* CreateTree(vector& tree_info, int num)
{
	//按照顺序存储树的各个节点并建立联系
	for (int i = 1; i <= num; ++i)
	{
		int l, r, val;
		cin >> l >> r >> val;
		if (l != 0)
		{
			tree_info[i].left = &tree_info[l];
		}
 
		if (r != 0)
		{
			tree_info[i].right = &tree_info[r];
		}
 
		tree_info[i].value = val;
	}
 
	return &tree_info[1];
}
 
Node* MergeTree(Node* root1,Node* root2)
{
	if (root1 != nullptr && root2 != nullptr)
	{
		root1->left = MergeTree(root1->left, root2->left);
		root1->right = MergeTree(root1->right, root2->right);
		root1->value += root2->value;
	}
 
	return root1 == nullptr ? root2 : root1;
 
}
 
void LevelOrder(Node* root) //DFS
{
	queue q;
	q.push(root);
 
	while (!q.empty())
	{
		int size = q.size();
		for (int i = 0; i < size; ++i)
		{
			Node* temp = q.front();
			q.pop();
			cout << temp->value << " ";
 
			if (temp->left != nullptr)
				q.push(temp->left);
 
			if (temp->right != nullptr)
				q.push(temp->right);
		}
	}
	cout << endl;
}
 
 
 
int main()
{
	int m = 0;
	int n = 0;
	cin >> m >> n;
 
	vector tree_m(m + 1);
	vector tree_n(n + 1);
 
 
 
	Node* root1 = CreateTree(tree_m, m);
	Node* root2 = CreateTree(tree_n, n);
 
	Node* root = MergeTree(root1, root2);
 
	LevelOrder(root);
 
	return 0;
}