二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下,恢复这棵树。
示例 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=tempreturn}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)}
推荐阅读
喜欢本文的朋友,欢迎关注“Go语言中文网”:
Go语言中文网启用微信学习交流群,欢迎加微信:274768166