golang中怎么利用leetcode 恢复二叉搜索树，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:
计算
安全
数据库
网络和加速
企业服务
输入: [1,3,null,null,2] 1 / 3 \ 2输出: [3,1,null,null,2] 3 / 1 \ 2示例 2:
输入: [3,1,4,null,null,2] 3 / \1 4 / 2输出: [2,1,4,null,null,3] 2 / \1 4 / 3进阶:
使用 O(n) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗？
解题思路：
1，二叉树的性质：左子树<根<小于右子树
2，如果中序遍历二叉树就能得到一个递增的序列
3，由于只交换了两个位置，假设这两个位置为first，second，则first左边小于first，右边大于first，second的左边都小于second，只需交换first，second位置即可
4，如何得到递增序列？
中序遍历
5，用pre记录中序遍历的上一个位置，如果pre.val>cur.val说明pre的位置放错了，用first，second 记录两个位置，最好交换即可
6，注意，由于使用了全局指针，所以，使用前一定要初始化，否则结果很奇怪
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */var pre,first,second *TreeNodefunc recoverTree(root *TreeNode) { pre=nil first=nil second =nil midOrder(root) temp:=first.Val first.Val=second.Val second.Val=temp return}func midOrder(cur *TreeNode){ if cur==nil{ return } midOrder(cur.Left) if pre!=nil && pre.Val>cur.Val{ if first==nil{ first=pre second=cur }else{ second=cur } } pre=cur midOrder(cur.Right)}看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注亿速云行业资讯频道，感谢您对亿速云的支持。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/4586289/blog/4634835
