c - 使用 C 将二叉树就地转换为二叉搜索树

Question

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

BTtoBST(节点*根)

1.如果根为NULL返回

2.其他当前=根

3.if (current->left > current) 交换(current->left , current)

4.if (current->right < current) 交换(current->right , current)

5.current=current->left

6 转到 3 如果当前！=NULL 否则转到 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指针。