在Java中合并二叉树

Question

我已经在“合并两棵二叉树”上工作了好几个小时了，我不明白为什么我的代码不起作用。树t1被指定为[1,3,2,5]，树t2被指定为[2,1,3，null，4，null，7]，我必须通过对重叠节点求和并尽可能避免null来合并这两棵树，因此结果应该是[3,4,5,5,4，null，7]。我不是像我应该的那样创建一棵新树，而是重写树t1以获得所需的结果。我的代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        traversal(t1, t2);
        return t1;
    }

    public void traversal(TreeNode t1, TreeNode t2) {
        if(t2 == null) return;
        if(t1 == null)
            t1 = new TreeNode(0);
        t1.val += t2.val;
        traversal(t1.left, t2.left);
        traversal(t1.right, t2.right);
    }
}

我的代码运行时没有错误，我的最终结果是[3,4,5,5]，这显然是错误的。好像是排队

t1 = new TreeNode(0);

不是在做我想让它做的事。我希望它将当前节点从空变为0，左节点为空，右节点为空，这样在下一次迭代中，程序将迭代新创建的空左节点。

我试着在我的IDE中重新创建整个东西（包括类/方法声明），以便使用它并进行一些调试，这样如果需要的话，我可以在本文中编辑我的完整代码，但我也不知道该怎么做

TreeNode(int val, TreeNode left, TreeNode right) {
  this.val = val;
  this.left = left;
  this.right = right;
}

当我希望左边或右边（但不是两者）都为空时，我的完整代码就没有应该的那么干净了。在任何情况下，有人能帮我找出为什么我的代码在给定的输入中得到错误的答案吗？

Answer 1

我猜你的问题在于下面的代码并没有真正达到你的目的。

public void traversal(TreeNode t1, TreeNode t2) {
. . .
if(t1 == null)
    t1 = new TreeNode(0);
. . .

在这里，您可以将引用的本地副本更改为指向新对象。您不会更改原始对象。事实上，与最初创建对象的原始方法不同，您不能使用其他方法来实现这一点。请参阅java传递值。

所以基本上您创建了一个新的TreeNode，它没有连接到父节点。您必须手动执行，同时跟踪父节点。