41. 合并二叉树 已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。C语言的

实现如下：

#include <stdio.h>
#include <stdlib.h>

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

struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) {
    if (t1 == NULL) return t2;
    if (t2 == NULL) return t1;
    t1->val += t2->val;
    t1->left = mergeTrees(t1->left, t2->left);
    t1->right = mergeTrees(t1->right, t2->right);
    return t1;
}

int main() {
    // 构造两棵树
    struct TreeNode *t1 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    struct TreeNode *t2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t1->val = 1;
    t1->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t1->left->val = 3;
    t1->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t1->left->left->val = 5;
    t1->left->left->left = NULL;
    t1->left->left->right = NULL;
    t1->left->right = NULL;
    t1->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t1->right->val = 2;
    t1->right->left = NULL;
    t1->right->right = NULL;

    t2->val = 2;
    t2->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t2->left->val = 1;
    t2->left->left = NULL;
    t2->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t2->left->right->val = 4;
    t2->left->right->left = NULL;
    t2->left->right->right = NULL;
    t2->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t2->right->val = 3;
    t2->right->left = NULL;
    t2->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t2->right->right->val = 7;
    t2->right->right->left = NULL;
    t2->right->right->right = NULL;

    // 合并两棵树
    struct TreeNode *t = mergeTrees(t1, t2);

    // 输出合并后的树
    printf("%d\n", t->val);
    printf("%d %d\n", t->left->val, t->right->val);
    printf("%d %d %d %d\n", t->left->left->val, t->left->right->val, t->right->left->val, t->right->right->val);

    return 0;
}

该程序的输出结果为：

3
4 5
5 4 7 0