通过插入镜像 BST

Question

Write a function in C to create a new BST which is the mirror image of a given tree.

我想到了这个问题的一个实现，它只是从原始树中复制根节点，然后通过 DFS 遍历发现新节点并将它们插入到具有不同比较函数的新镜像树中（即使用> 而不是 < 在遍历和插入节点时）。

我的问题是：这种方法是否适用于所有情况？我想是的，但我想知道是否存在我的解决方案不起作用的极端情况（或者是否有更好的解决方案）。

Answer 1

递归求解：镜像左右子节点，分别作为镜像节点的左右子节点。下面的代码（调用 mirrorTree(root) 来执行）：

class Node:
  def __init__(self, val, left, right):
    self.val=val
    self.left=left
    self.right=right

def mirrorTree(node):
  new_node=None
  if node:
    new_node=Node(node.val, mirrorTree(node.right), mirrorTree(node.left))
  return new_node

Answer 2

与 gen-y-s 相同的答案，但只是在 C 中。

    node *create_empty()
    {
            node *temp = malloc(sizeof(*temp));
            temp->left = left;
            temp->right = right;
            return temp;
    }

    node *add_detail(int value, node *left, node *right)
    {
            temp->value = value;
            temp->left = left;
            temp->right = right;
            return temp;
    }

    node *mirror(node *p)
    {
            if (p) {
                    node = create_empty();
                    node = add_detail(p->value, mirror(p->right), mirror(p->left));
            }
            return node;
    }

通过插入镜像 BST

Mirroring BSTs by insertion

algorithm

binary-search-tree