C++算法练习-day40——617.合并二叉树

题目来源：. - 力扣（LeetCode）

题目思路分析

题目：给定两棵二叉树 root1 和 root2，请合并这两棵树，即将 root2 中的每个节点合并到 root1 中，合并的规则是如果两个节点在同一位置（即具有相同的深度），则将它们的值相加。如果某个节点在 root1 中不存在，而在 root2 中存在，则直接将这个节点添加到 root1 中。

思路：

1. 递归遍历：由于树的性质，我们可以使用递归的方法来遍历树的每个节点。
2. 节点处理：对于每对对应节点（root1 和 root2 中的同一位置的节点）：
   • 如果两个节点都存在，则创建一个新节点，其值为两个节点值的和。
   • 如果其中一个节点不存在，则直接返回另一个节点（即如果 root1 中没有节点而 root2 中有，则直接返回 root2 的节点，反之亦然）。
3. 递归调用：对左右子树递归调用合并函数。

代码:

/**  
 * 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) {  
        // 如果 root1 为空，直接返回 root2，因为要将 root2 合并到 root1 中  
        if(!root1){  
            return root2;  
        }  
        // 如果 root2 为空，直接返回 root1，因为 root1 没有变化  
        if(!root2){  
            return root1;  
        }  
          
        // 创建一个新节点，其值为两个节点值的和  
        TreeNode* node=new TreeNode(root1->val+root2->val);  
          
        // 递归调用 mergeTrees 合并左子树  
        node->left=mergeTrees(root1->left,root2->left);  
          
        // 递归调用 mergeTrees 合并右子树  
        node->right=mergeTrees(root1->right,root2->right);  
          
        // 返回合并后的新树的根节点  
        return node;  
    }  
};

知识点摘要

1. 二叉树遍历：二叉树的遍历方式有前序、中序和后序遍历，以及层次遍历。本题使用了递归的方式遍历二叉树。
2. 递归思想：递归是一种在函数内调用自身的编程技巧，适用于解决可以分解为相似子问题的问题。
3. 动态内存分配：使用 new 关键字在堆上动态分配内存，用于创建新的节点。

通过这道题目，我们学习了如何使用递归方法合并两棵二叉树。递归的核心在于将大问题分解为小问题，并解决小问题，然后将结果组合起来解决大问题。在本题中，我们通过递归遍历树的每个节点，并合并对应位置的节点值，最终得到了合并后的树。这种方法不仅直观易懂，而且能够高效地解决问题。在实际应用中，递归方法在处理树结构或图结构的问题时非常有用，值得我们深入学习和掌握。