每日一题--合并二叉树

合并二叉树

问题描述

已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：如果节点存在于两棵树中，则将节点值相加；如果某个节点在一棵树中不存在，则直接使用另一棵树的节点值。例如：

两颗二叉树如下：

Tree 1

       1/   \3     2/5

Tree 2

       2/   \1     3\     \4     7

合并后的二叉树应该是：

       3/   \4     5/ \     \5   4     7

数据范围

• 树上节点数量：$0\le n\le 500$
• 每个节点的值在32位整型范围内。

进阶要求

• 空间复杂度：$O(1)$
• 时间复杂度：$O(n)$

示例

• 输入1：

  {1,3,2,5},{2,1,3,#,4,#,7}
  

  返回值：

  {3,4,5,5,4,#,7}
  

• 输入2：

  {1},{}
  

  返回值：

  {1}
  

代码实现

/*** struct TreeNode {*  int val;*  struct TreeNode *left;*  struct TreeNode *right;* };*//*** 创建一个新的节点* @param val 节点的值* @return 创建的节点*/
struct TreeNode* createNode(int val ) {struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));newNode->val = val;newNode->left = NULL;newNode->right = NULL;return newNode;
}/*** 递归遍历两个树并合并它们* @param root1 树1的当前节点* @param root2 树2的当前节点* @return 合并后的新节点*/
struct TreeNode* Traversal(struct TreeNode* root1, struct TreeNode* root2) {// 如果两个节点都为空，返回NULLif (!root1 && !root2) return NULL;// 创建一个新的节点来保存合并后的结果struct TreeNode* newNode = createNode(0);// 如果树1存在节点，则将其值加到新节点if (root1) {newNode->val += root1->val;}// 如果树2存在节点，则将其值加到新节点if (root2) {newNode->val += root2->val;}// 递归合并左子树newNode->left = Traversal(root1 ? root1->left : NULL, root2 ? root2->left : NULL);// 递归合并右子树newNode->right = Traversal(root1 ? root1->right : NULL, root2 ? root2->right : NULL);return newNode;
}/*** 合并两棵二叉树* @param t1 树1的根节点* @param t2 树2的根节点* @return 合并后的树的根节点*/
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) {// 调用递归函数进行树的合并return Traversal(t1, t2);
}

代码说明

1. 创建节点：createNode(int val)函数用于创建一个新的树节点，并将其左指针和右指针初始化为NULL。

2. 递归合并：Traversal(struct TreeNode* root1, struct TreeNode* root2)函数使用递归遍历树1和树2。当树1和树2的对应节点存在时，将节点的值相加，并继续合并左子树和右子树。如果某一棵树的节点为空，则直接使用另一棵树的节点。

3. 合并入口：mergeTrees(struct TreeNode* t1, struct TreeNode* t2)函数是合并两棵二叉树的入口函数。它调用Traversal函数来进行递归合并。

总结

这道题目主要考察如何通过递归遍历两棵二叉树并将它们合并为一棵新的树。在合并过程中，如果某个节点在其中一棵树中不存在，就用另一棵树的节点来替代。通过递归的方式，我们可以高效地合并两棵树。