二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下,恢复这棵树。
示例 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
进阶:
解题思路:
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 *TreeNode
func 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)
}
本文分享自 golang算法架构leetcode技术php 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!