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

Question

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

BTtoBST(节点*根)

1.如果root为NULL则返回

2.else current=root

3.if(当前->左>当前)交换(当前->左,当前)

4.if(当前->右<当前)swap(当前->右,当前)

5.current=当前->左

6 如果当前!=NULL，则转到 3，否则转到 4

7.current=当前->右

提前致谢

PS:我看到了这个链接，但没有多大帮助! Convert Binary Tree -> BST (maintaining original tree shape)

Answer 1

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

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