algorithm - 有人能解释一下如何合并两个二叉树吗？

Question

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

你需要将它们合并成一个新的二叉树。合并规则是，如果两个节点重叠，则将节点值相加作为合并节点的新值。否则，NOT null节点将被用作新树的节点。

输入:

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.val += t2.val;，您可以看出我们实际上是在将树 2 合并到树 1。我们并没有创建新树/节点。

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

只有当我们处理了当前节点的左右子树(如果有的话)时，我们才返回 t2 或 t1。此返回值成为先前调用mergeTrees() 时t1 节点的子节点。

例子:

Tree 1:
  a (single node)

Tree 2:
  b
 /
c

第一个函数调用 - mergeTrees(a, b):

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

所以我们进行第二次函数调用 - mergeTrees(null, c):

• 这里的第一个节点是空的。所以我们简单地返回另一个节点 c

现在，控制权回到第一个调用:

• a.left = c
• 我们必须将 a.right 分配给第三个函数调用返回的节点 - mergeTrees(a.right, b.right)

是时候进行第 3 次函数调用了 - mergeTrees(null, null):

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

控制回到第一次调用:

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

调用者现在收到合并树的根 a，现在看起来像这样:

Merged Tree:

  a
 /
c

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