C++二叉树的直径与合并详解

Owen

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

原创

本文讲解如何使用C++解决二叉树的两个经典问题：计算二叉树的直径以及合并两棵二叉树。通过深入分析递归逻辑与代码实现，帮助开发者掌握树结构遍历的核心技巧。

计算二叉树的直径

问题描述：给定一棵二叉树，需要计算其直径长度。二叉树的直径定义为任意两个结点之间路径长度的最大值。这条路径可能穿过根结点，也可能不穿过。

示例说明：

在图中，路径 [4,2,1,3] 或 [5,2,1,3] 的长度均为 3，这是该二叉树的最大直径。

解题思路

二叉树的直径本质上是某个节点的左子树高度与右子树高度之和的最大值。因此，我们可以通过深度优先搜索（DFS）遍历每个节点，同时计算以当前节点为“最高点”的路径长度（即左子树深度 + 右子树深度），并更新全局最大值。

C++ 代码实现

/**
 * 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:
    int res = 0; // 用于记录最大直径

    // 辅助函数：计算节点深度
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        
        // 递归计算左右子树的深度
        int L = depth(root->left);
        int R = depth(root->right);
        
        // 更新全局最大直径：当前节点左高 + 右高
        res = max(res, L + R);
        
        // 返回当前节点的深度（取左右子树较大值 + 1）
        return max(L, R) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        depth(root); // 触发递归遍历
        return res;
    }
};

合并二叉树

问题描述：给定两棵二叉树，想象将它们覆盖在一起，重叠的节点会合并。合并规则如下：

如果两个节点重叠，则将它们的值相加作为新节点的值。
如果其中一个节点为空，则另一个非空节点直接作为新二叉树的节点。

示例 1：

解题思路

合并操作天然适合使用递归解决。我们可以定义一个递归函数，接收两棵树的根节点作为参数，并按以下步骤处理：

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

我们需要传入两棵二叉树的根节点 t1 和 t2，返回值是合并后新二叉树的根节点。函数签名大致如下：

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

第2步：确定终止条件

由于同时遍历两棵树，当其中一棵树的节点为空时，递归应直接返回另一棵树的对应节点：
- 若 t1 为空，返回 t2。
- 若 t2 为空，返回 t1。
这样既处理了边界情况，也避免了空指针异常。

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

当两个节点都不为空时，我们将它们的值相加，赋值给 t1 的节点（就地修改）。然后递归地合并 t1 和 t2 的左子树和右子树，并将结果重新赋值给 t1 的左右指针。最终返回 t1 作为合并后的根节点。

C++ 代码实现

/**
 * 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 的值和结构
        root1->val += root2->val;
        
        // 递归合并左右子树
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        
        return root1;
    }
};