C++合并二叉树的递归思路与代码实现

清欢

发布时间：2026-10-16| 5人浏览过

原创

本文介绍在C++中合并两个二叉树的算法实现。合并规则为：若两节点重叠，则值相加；否则非空节点直接作为新树节点。文章通过递归方式解析思路，并提供修改原树结构和不破坏原结构的两种代码示例。

问题背景与目标

给定两个二叉树，将其中一个覆盖到另一个上时，部分节点会重叠。合并的规则如下：

如果两个节点重叠，将它们对应的值相加，作为新二叉树该节点的值。
如果其中任何一个节点不为 NULL，则该非空节点直接作为新二叉树的对应节点（即不需要创建新节点，直接复用或返回即可）。

核心思路解析

解决此问题最直观的方法是采用深度优先搜索（DFS）中的前序遍历递归思想。我们需要确定递归函数的三个要素：

第一步：确定递归函数的参数和返回值

由于需要合入两棵二叉树，函数至少需要传入两个二叉树的根节点 t1 和 t2。返回值则是合并后的新二叉树的根节点，类型同样为 TreeNode*。

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2)

第二步：确定终止条件

因为涉及两棵树的同步遍历，当遇到空节点时需特殊处理：

如果 t1 == NULL，说明t1在该位置已遍历结束，此时合并结果应直接返回 t2（即使 t2 也为 NULL，返回 NULL 也是正确的）。
反之，如果 t2 == NULL，则直接返回 t1。

这段逻辑天然处理了两个树长度不一致的情况：

if (t1 == NULL) return t2;
if (t2 == NULL) return t1;

第三步：确定单层递归逻辑

在终止条件之外，说明 t1 和 t2 均不为空。此时有两种常见的处理策略：

修改原有树结构（原地合并）：直接利用 t1 作为结果的根节点，将其值累加 t2 的值，然后递归处理左右子树。
新建一棵树：不改变原树，每次递归创建新节点来存储结果。

实战代码示例

策略一：修改原有树结构（推荐空间效率较高）

这种方法直接复用 t1 的节点对象，仅修改其值和指针指向，无需额外开辟大量内存创建新节点。

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        // 终止条件：如果任一节点为空，返回另一个节点
        if(root1==nullptr) return root2;
        if(root2==nullptr) return root1;

        // 累加当前节点值
        root1->val+=root2->val;
        
        // 递归合并左子树和右子树，并将结果赋值给root1的子节点
        root1->left=mergeTrees(root1->left, root2->left);
        root1->right=mergeTrees(root1->right, root2->right);
        
        return root1;
    }
};

策略二：新建一棵树（不破坏原结构）

如果业务要求保留原有的两棵二叉树不变，则需要创建一个新的节点 node。在创建节点时，需判断原节点是否为空，若为空则视为值0参与计算。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        // 如果两个都为空，直接返回空
        if(!t1 && !t2)
            return NULL;
            
        // 创建新节点，初始值为0
        TreeNode* node=new TreeNode(0);
        
        // 计算新节点的值：处理null情况，若为空则取0
        node->val=(t1 ? t1->val:0)+(t2 ? t2->val:0);
        
        // 递归构建左右子树，注意递归入口也要处理空指针
        node->left=mergeTrees((t1 ? t1->left : NULL),(t2 ? t2->left :NULL));
        node->right=mergeTrees((t1 ? t1->right : NULL),(t2 ? t2->right : NULL));
        
        return node;
    }
};