使用 C 将二叉树转换为二叉搜索树

Question

不使用任何额外的空间将二叉树转换为二叉搜索树。我想出了以下算法，但它不起作用。

BTtoBST(node *root)

1.如果 root 为 NULL 返回

2.else current=root

3.if (current->left > current) swap(current->left , current)

4.if (current->current) ;right < current) swap(current->right , current)

5.current=current->left

6 如果 current!=NULL 则转到 3 否则转到 4

7.current=current->right

提前致谢

PS：我看到了这个链接，但没有多大帮助！ 转换二叉树 -> BST（保持原始树形状）

Answer 1

您可以像在 AVL 树 http://en 中一样交换包括子树在内的节点（不仅仅是节点内容）。 wikipedia.org/wiki/AVL_tree

只要违反 BST 约束，就继续交换，每次交换后从根重新启动深度优先搜索。

Answer 2

对树执行后序（自下而上）遍历，获取访问过的节点并将它们插入到 BST 中。

“没有任何额外空间”是否排除递归？

如果不是，那么类似：

# top level call passes null for bst
bt_to_bst (root, bst)
  # nothing to add to bst; just return it
  if null(root) -> return bst
  # if this is a leaf node, stick it into the BST
  if null(root->left) && null(root->right)
    return bst_insert(bst, root)
  # otherwise add all of left subtree into the bst and then the right tree
  bst = bt_to_bst (root->left, bst);
  return bt_to_bst (root->right, bst);

bt_to_bst 是一个过滤操作；它需要一个现有的 bst 并返回一个新的 bst，其中添加了给定的节点。

向 bst 添加叶节点是安全的，因为我们永远不会再访问它，因此我们可以覆盖它的 left 和 right 指针。