两种递归方法之间的区别

我想反映一个二叉树，使左边的所有节点都结束在右边，反之亦然。两种递归方法之间的区别

喜欢的东西：

  A 
    / \ 
    B  C 
/ / \ 
D  E  F

将成为

  A 
    / \ 
    C  B 
/\  \ 
F  E  D

我注意到，在写我的解决方案，这个代码工作：

static Tree getReflection(Tree root) { 
    if(root == null) { 
     return null; 
    } 
    Tree reflect = root; 
    Tree subRight = getReflection(root.right); 
    Tree subLeft = getReflection(root.left); 
    reflect.left = subRight; 
    reflect.right = subLeft; 
    return reflect; 
}

然而，这一次没有按” t：

static Tree getReflection(Tree root) { 
    if(root == null) { 
     return null; 
    } 
    Tree reflect = root; 
    reflect.left = getReflection(root.right); 
    reflect.right = getReflection(root.left); 
    return reflect; 
}

有人可以向我解释为什么？对我来说，除了使用临时树变量外，它们看起来像是相同的方法。

来源

2016-03-02 Fiass

看看在每个第一条语句：当你将

反映=根

，这两个变量现在都指向同一个内存位置。现在，让我们来看看第二个程序的运行：

Tree reflect = root; 
// reflect and root now refer to exactly the same tree. 
reflect.left = getReflection(root.right); 
// reflect the right subtree; make that the new left subtree. 
reflect.right = getReflection(root.left); 
// Grab that new subtree, re-reflect it, and put it back on the right.

原来的左子树丢失，由右侧的反射所取代。

在第一个例程中，您将它们保存在局部变量中，直到完成两次反射为止。

来源

2016-03-02 02:21:09 Prune

所以我应该做一些像Tree reflect = new Tree（root.value）的东西。那么它会创建一个新对象而不是指向原始根的指针？这个想法是否正确？ – Fiass

没错。你必须以某种方式得到新的副本，并且你的建议可以做到。 – Prune

这是因为在第二个函数（不工作的函数）中，您将反射结果分配给您的左节点，然后将其用作您分配给右节点的反射的输入。

树反射= 根;

reflect.left = getReflection（root.right）;

reflect.right = getReflection（root.left）;

来源

2016-03-02 02:20:48 qexyn

两种递归方法之间的区别

回答

相关问题