两种递归方法的区别

Question

我想反映一个二叉树，这样左边的所有节点都在右边，反之亦然。

类似于：

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

然而，这个没有：

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

谁能给我解释一下为什么？对我来说，它们看起来像是相同的方法，除了一个使用临时树变量。

Answer 1

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

树反射=根;

reflect.left = getReflection(root.right);

reflect.right = getReflection(root.left);

Answer 2

查看每个中的第一个语句：当您分配

reflect = root

，这两个变量现在指向相同的内存位置。下面我们来看第二个例程的运行：

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.

原来的左子树丢失了，取而代之的是右子树的反射。

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

两种递归方法的区别

Difference Between Two Recursive Methods

recursion

binary-tree