扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
golang中怎么利用leetcode 恢复二叉搜索树，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。
创新互联公司是一家专注网站建设、网络营销策划、微信平台小程序开发、电子商务建设、网络推广、移动互联开发、研究、服务为一体的技术型公司。公司成立10余年以来，已经为上1000+成都被动防护网各业的企业公司提供互联网服务。现在，服务的上1000+客户与我们一路同行，见证我们的成长；未来，我们一起分享成功的喜悦。
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 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=nilfirst=nilsecond =nilmidOrder(root)temp:=first.Valfirst.Val=second.Valsecond.Val=tempreturn}func midOrder(cur *TreeNode){if cur==nil{return}midOrder(cur.Left)if pre!=nil && pre.Val>cur.Val{if first==nil{first=presecond=cur}else{second=cur}}pre=curmidOrder(cur.Right)}
看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注创新互联行业资讯频道，感谢您对创新互联的支持。
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网