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);

不是在做我希望它做的事情。我希望它将当前节点从null更改为值0、null左节点和null右节点，以便在下一次迭代中，程序将迭代新创建的null左节点。

我试着在IDE中重新创建整个东西(包括类/方法声明(，以便对其进行处理和调试，因此如果需要，我可以将完整的代码编辑到本文中，但我也不知道如何进行

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

当我希望左边或右边(但不是两者都是(为null时，我的完整代码并没有达到应有的干净程度。无论如何，有人能帮我弄清楚为什么我的代码对给定的输入得到了错误的答案吗？

Answer 1

我想你的问题是下面的代码并没有真正做到你想要做的。

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

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

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