每日一题——合并二叉树

题目

---

已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：

两颗二叉树是:
Tree 1

Tree 2

合并后的树为

数据范围：树上节点数量满足 0≤n≤500，树上节点的值一定在32位整型范围内。

进阶：空间复杂度 O(1) ，时间复杂度 O(n)

参数说明：二叉树类，二叉树序列化是通过按层遍历,#代表这这个节点为空节点，举个例子：

  1
 / \
2   3
   /
  4

以上二叉树会被序列化为 {1,2,3,#,#,4}

示例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;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        // write code here
        if (t1 == nullptr) {
            return t2;
        } else if (t2 == nullptr) {
            return t1;
        }

        // 前序递归
        auto head = new TreeNode(t1->val + t2->val);
        head->left = mergeTrees(t1->left, t2->left);
        head->right = mergeTrees(t1->right, t2->right);
        return head;
    }
};