D (1173) : A DS二叉树_合并二叉树

一、题目描述

给定两个二叉树，输出这两个二叉树合并后形成的二叉树，依次输出前序遍历、中序遍历、后序遍历。

二、输入与输出

1.输入

第一行输入t，表示有t个测试样例。
第二行首先输入n1，接着输入n1个整数，用于代表二叉树tree1。
第三行首先输入n2，接着输入n2个整数，用于代表二叉树tree2。
以此类推，每两行输入一个测试样例的两个二叉树。
共输入t个测试样例。
数组形式的二叉树表示方法与题目：DS二叉树_伪层序遍历构建二叉树 相同，输入-1表示空结点。

5
4 1 3 2 5
7 2 1 3 -1 4 -1 7

1 1
1 1

5 1 2 -1 3 4
1 1

1 1
5 1 2 3 -1 4

4 1 2 -1 3
5 1 -1 2 -1 3

2.输出

每三行依次输出合并后的二叉树的前序遍历、中序遍历、后序遍历。
共输出t个二叉树。
注意输出末尾的空格。

3 4 5 4 5 7 
5 4 4 3 5 7 
5 4 4 7 5 3 

2 
2 
2 

2 2 3 4 
3 2 4 2 
3 4 2 2 

2 2 4 3 
2 4 2 3 
4 2 3 2 

2 2 3 2 3 
3 2 2 2 3 
3 2 3 2 2 

三、参考代码

#include <iostream>
#include <string>
#include<stack>
#include<queue>
using namespace std;

class TreeNode
{
public:
    int data;
    TreeNode* lchild;
    TreeNode* rchild;
    TreeNode* parent;
    TreeNode() {};
    TreeNode(int num) { parent = NULL, rchild = NULL; lchild = NULL; data = num; }
    
};

TreeNode* Create(int arr[], int num)
{
    if (num == 0)
    {
        return NULL;
    }


    queue<TreeNode*> q;
    TreeNode* root = new TreeNode(arr[0]);
    q.push(root);

    int index = 1;
    while (!q.empty() && index < num)
    {
        TreeNode* now = q.front();
        q.pop();

        if (index < num && arr[index] != -1)
        {
            now->lchild = new TreeNode(arr[index]);
            q.push(now->lchild);
        }
        index++;

        if (index < num && arr[index] != -1)
        {
            now->rchild = new TreeNode(arr[index]);
            q.push(now->rchild);
        }
        index++;
    }
    return root;
}

TreeNode* Together(TreeNode* t1, TreeNode* t2)
{
    if (!t1 && !t2) return NULL;
    if (!t1) return t2;
    if (!t2) return t1;

    TreeNode* cur = new TreeNode(t1->data + t2->data);
    cur->lchild = Together(t1->lchild, t2->lchild);
    cur->rchild = Together(t1->rchild, t2->rchild);
    return cur;
}

void Prepri(TreeNode* t)//前序
{
    if (t)
    {
        cout << t->data << " ";
        Prepri(t->lchild);
        Prepri(t->rchild);
    }
}
void Pospri(TreeNode* t)//后序
{
    if (t)
    {
        Pospri(t->lchild);
        Pospri(t->rchild);
        cout << t->data << " ";

    }
}
void Inpri(TreeNode* t)//中序
{
    if (t)
    {
        Inpri(t->lchild);
        cout << t->data << " ";
        Inpri(t->rchild);
    }
}

void pri(TreeNode* t)
{
    Prepri(t);
    cout << endl;
    Inpri(t);
    cout << endl;
    Pospri(t);
    cout << endl;
    cout << endl;
}

int main()
{
    int sum;
    cin >> sum;
    int num1 = 0;
    int num2 = 0;
    int flag = 0;
    while (sum--)
    {
        cin >> num1;
        int* arr1 = new int[num1];
        for (int i = 0; i < num1; i++)
        {
            cin >> arr1[i];
        }
        TreeNode* t1 = Create(arr1, num1);

        cin >> num2;
        int* arr2 = new int[num2];
        for (int i = 0; i < num2; i++)
        {
            cin >> arr2[i];
        }
        TreeNode* t2 = Create(arr2, num2);


        TreeNode* t = Together(t1, t2);

        pri(t);

    }


    return 0;
}