C++算法练习-day40——617.合并二叉树
题目来源：. - 力扣（LeetCode）
题目思路分析
题目：给定两棵二叉树 root1 和 root2，请合并这两棵树，即将 root2 中的每个节点合并到 root1 中，合并的规则是如果两个节点在同一位置（即具有相同的深度），则将它们的值相加。如果某个节点在 root1 中不存在，而在 root2 中存在，则直接将这个节点添加到 root1 中。
思路：
- 递归遍历：由于树的性质，我们可以使用递归的方法来遍历树的每个节点。
- 节点处理：对于每对对应节点（
root1和root2中的同一位置的节点）：- 如果两个节点都存在，则创建一个新节点，其值为两个节点值的和。
- 如果其中一个节点不存在，则直接返回另一个节点（即如果
root1中没有节点而root2中有，则直接返回root2的节点，反之亦然）。
- 递归调用：对左右子树递归调用合并函数。
代码:
/** * 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; }
};知识点摘要
- 二叉树遍历：二叉树的遍历方式有前序、中序和后序遍历，以及层次遍历。本题使用了递归的方式遍历二叉树。
- 递归思想：递归是一种在函数内调用自身的编程技巧，适用于解决可以分解为相似子问题的问题。
- 动态内存分配：使用
new关键字在堆上动态分配内存，用于创建新的节点。
通过这道题目，我们学习了如何使用递归方法合并两棵二叉树。递归的核心在于将大问题分解为小问题，并解决小问题，然后将结果组合起来解决大问题。在本题中，我们通过递归遍历树的每个节点，并合并对应位置的节点值，最终得到了合并后的树。这种方法不仅直观易懂，而且能够高效地解决问题。在实际应用中，递归方法在处理树结构或图结构的问题时非常有用，值得我们深入学习和掌握。