关于面试:每日一题合并二叉树

题目

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

两颗二叉树是:
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;
    }
};