搜索二叉树两个子节点互换,恢复之

首先要了解什么是搜索二叉树(或者界查找二叉树):

它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树


给出两种解法。

第一种比较巧妙,在中序遍历的过程中不断查找是否有节点的值异常(所谓异常就是因为搜索二叉树的值永远是:左子树<根<右子树,找到不符合这样情况的节点),分别存放到a,b中去,最后在互换过来。



第二种索性先把搜索二叉树所有的节点按中序遍历一遍放到容器中去,再直接将容器中的元素从小到大排序,一个For循环创建容器中元素个数的节点,每个节点的值都对应着容器中的元素值。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容