本文共 2130 字，大约阅读时间需要 7 分钟。

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

Input: 	Tree 1                     Tree 2                            1                         2                                      / \                       / \                                    3   2                     1   3                               /                           \   \                            5                             4   7                  Output: Merged tree:	     3	    / \	   4   5	  / \   \ 	 5   4   7

Note: The merging process must start from the root nodes of both trees.

题意：合并两个二叉树，规则是如果两个结点重叠，就将它们的值相加作为新值。

提示：对于这种题，如果在面试之中，需要询问：

• 是否可以在原树上进行修改，或者必须创建新树；
• 两个结点的值相加可能溢出吗？

思路1

先序合并，在原树上修改。如果都为空，直接返回；如果都非空，则修改 t1->val ；如果只存在 t2 ，则创建新结点，值为 t2->val ，赋给 t1 。然后递归合并两棵树的左右子树，注意不能访问空结点。代码如下：

class Solution {
   public:    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
           if (!t1 && !t2) return t1;        if (t1 && t2) t1->val += t2->val;         else if (t2) t1 = new TreeNode( t2->val);           t1->left = mergeTrees(t1 ? t1->left : nullptr, t2 ? t2->left : nullptr);        t1->right = mergeTrees(t1 ? t1->right : nullptr, t2 ? t2->right  : nullptr);        return t1;    }};

效率如下：

执行用时：84 ms, 在所有 C++ 提交中击败了35.19% 的用户内存消耗：32.2 MB, 在所有 C++ 提交中击败了82.96% 的用户

思路2

上面的做法有点奇葩，其实我一时想叉了，没注意到题面：不为空的结点将直接作为新二叉树的结点。所以，如果 t1 || t2 时，直接返回 t1 ? t1 : t2 即可，实际上相当于返回了这个非空结点携带的子树。修改后的代码如下，

class Solution {
   public:    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
           if (!t1 && !t2) return t1;         if (t1 && t2) {
               t1->val += t2->val;              t1->left = mergeTrees(t1->left, t2->left);            t1->right = mergeTrees(t1->right, t2->right);        }        return (t1 ? t1 : t2);    }};

效率如下：

执行用时：80 ms, 在所有 C++ 提交中击败了51.28% 的用户内存消耗：32.2 MB, 在所有 C++ 提交中击败了75.88% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/108761805 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！