有人能解释一下两棵二叉树是如何合并的吗？

Question

给定两棵二叉树，想象一下，当您将其中一棵树覆盖另一棵树时，两棵树的一些节点重叠，而其他节点则不重叠。

您需要将它们合并到一个新的二叉树中。合并规则是，如果两个节点重叠，则将节点值加起来作为合并节点的新值。否则，非空节点将用作新树的节点。

输入：

Tree 1                     Tree 2                  
      1                         2                             
     / \                       / \                            
    3   2                     1   3                        
   /                           \   \                      
  5                             4   7                  

输出：合并树：

     3
    / \
   4   5
  / \   \ 
 5   4   7



public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null)
            return t2;
        if (t2 == null)
            return t1;
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}

问这个问题可能很幼稚，但这个算法是如何工作的？一旦我们返回这个t2或t1，它就会返回另一个TreeNode，所以从技术上讲，方法应该停止执行。不是吗？帮助我

Answer 1

这个算法

基本情况：节点t1、t2或两者均为空，因此该节点将被替换为其中之一（简单）

另一种情况更简单，这个算法首先访问节点，然后在这2棵树的左侧节点上进行递归，然后在右侧，所以它从顶部（根）开始，向下到左侧节点，当它到达最左侧的节点时，它会到达右侧节点，在并且您已经通过了树的所有节点。

只有t1被修改并返回，t2将被忽略。

https://imgur.com/NyDMFge

Answer 2

mergeTrees仅当“另一个TreeNode”是唯一的TreeNode时返回“另一个TreeNode”（因为其中一个为空），这是有意义的，因为在该子树上没有什么可以做的。但你仍然需要回去工作；特别是，您需要将“另一个TreeNode”附加到它的新父节点，并创建尚未访问的子树。

Answer 3

如果你注意这一行：t1。val=t2。瓦尔 ，可以看出我们实际上是在将树2合并到树1中。我们没有创建新的树/节点。

还要注意，我们总是在函数mergeTrees（）中传递两棵树的相应节点。如果两个节点都非空，我们将t2的值添加到t1中。如果其中任何一个为null，那么根据规则，我们必须保留另一个节点（可以是非null或null）。

只有在处理了当前节点的左右子树（如果有的话）之后，我们才会返回t2或t1。此返回值成为上一次调用mergeTrees（）时t1节点的子节点。

例子：

Tree 1:
  a (single node)

Tree 2:
  b
 /
c

第一个函数调用-合并树（a，b）：

• 这里的a和b节点都是非空的。所以我们做了a.val=b.val
• 现在，a.left将被分配给第二次函数调用返回的节点-mergeTrees（a.left，b.left）

所以我们进行第二次函数调用-mergeTrees（null， c）：

• 这里的第一个节点为空。因此，我们只需返回另一个节点c

现在，控制返回到第一个呼叫：

• a.left=c

是时候进行第三次函数调用了-mergeTrees（null， null）：

• 这里第一个节点为空。我们返回第二个节点，它也是null

控制室回到第一次通话：

• a.right=NULL
• 我们已经处理了左右子树。返回a。

调用者现在接收合并树的根a，它现在看起来像这样：

Merged Tree:

  a
 /
c

请注意，节点a现在存储值a.val b.val。