国外营销企业网站,苏州网站提升排名,青岛网站关键词,wordpress插件验证题目来源#xff1a;. - 力扣#xff08;LeetCode#xff09;
题目思路分析
题目#xff1a;给定两棵二叉树 root1 和 root2#xff0c;请合并这两棵树#xff0c;即将 root2 中的每个节点合并到 root1 中#xff0c;合并的规则是如果两个节点在同一位置#xff08;即…题目来源. - 力扣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* nodenew TreeNode(root1-valroot2-val); // 递归调用 mergeTrees 合并左子树 node-leftmergeTrees(root1-left,root2-left); // 递归调用 mergeTrees 合并右子树 node-rightmergeTrees(root1-right,root2-right); // 返回合并后的新树的根节点 return node; }
};
知识点摘要
二叉树遍历二叉树的遍历方式有前序、中序和后序遍历以及层次遍历。本题使用了递归的方式遍历二叉树。递归思想递归是一种在函数内调用自身的编程技巧适用于解决可以分解为相似子问题的问题。动态内存分配使用 new 关键字在堆上动态分配内存用于创建新的节点。
通过这道题目我们学习了如何使用递归方法合并两棵二叉树。递归的核心在于将大问题分解为小问题并解决小问题然后将结果组合起来解决大问题。在本题中我们通过递归遍历树的每个节点并合并对应位置的节点值最终得到了合并后的树。这种方法不仅直观易懂而且能够高效地解决问题。在实际应用中递归方法在处理树结构或图结构的问题时非常有用值得我们深入学习和掌握。
