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

题目

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

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