java - 使用递归镜像二叉搜索树

Question

在练习二叉搜索树时寻求一些帮助。我无法弄清楚代码中哪里出了问题，因为它似乎遵循通用递归格式。可能与临时节点或返回语句相关？任何帮助将不胜感激，谢谢。

public static Node < Integer > mirror(Node < Integer > root) {

    if (root == null)
        return null;
    else {

        mirror(root.left);
        mirror(root.right);

        Node temp = root.left;
        root.left = root.right;
        root.right = temp;

        return root;

    }

} 

Answer 1

首先，您似乎没有为属于镜像树的节点分配内存。注意指令

Node temp;

不在堆中分配，而是在栈中分配。当函数返回时，该内存将被释放，您存储在那里的任何内容都将不再有意义。

其次，您似乎没有非常清楚的遍历模式，我认为这是因为该行

root.right = temp;

构成一种不对称。

这是一种获取使用预序模式的镜像二叉树的方法(使用 C++ 伪代码):

Node * mirror(Node * root)
{
  if root == NULL
    return NULL;

  Node * mirror_root = new Node;
  mirror_root->left = mirror(root->right); // here is where the mirroring happens
  mirror_root->right = mirror(root->left);

  return mirror_root;
}

您可以尝试执行相同的操作，按后序或中序分配节点。