C 语言实现二叉树合并算法

C 语言实现二叉树合并算法

本文将提供 C 语言代码实现二叉树合并算法。输入两个二叉树的根节点，返回合并后的二叉树根节点。

代码实现

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;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = t1->val + t2->val;
    root->left = mergeTrees(t1->left, t2->left);
    root->right = mergeTrees(t1->right, t2->right);
    return root;
}

代码解释

1. 定义 TreeNode 结构体: 表示二叉树的节点，包含节点的值 val 和指向左右子节点的指针 left 和 right。

2. mergeTrees 函数: 接受两个二叉树的根节点 t1 和 t2 作为参数，返回合并后的二叉树根节点。

3. 递归处理: 首先判断 t1 和 t2 是否为空，如果其中一个为空，直接返回另一个。

4. 创建新节点: 创建一个新的节点 root，并将 root->val 设置为 t1->val + t2->val。

5. 递归合并子树: 递归调用 mergeTrees 函数合并 t1 和 t2 的左子树和右子树，并将结果分别赋值给 root->left 和 root->right。

6. 返回根节点: 最终返回合并后的二叉树的根节点 root。

代码使用示例

// ... (TreeNode 结构体定义)

int main() {
    // 创建两个示例二叉树
    struct TreeNode* t1 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t1->val = 1;
    t1->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t1->left->val = 3;
    t1->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    t1->right->val = 2;

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

    // 合并二叉树
    struct TreeNode* mergedTree = mergeTrees(t1, t2);

    // 打印合并后的二叉树 (省略打印逻辑)
    // ...

    return 0;
}

总结

本文展示了使用 C 语言实现二叉树合并算法的代码和详细解释，代码简洁易懂，方便理解和学习。