Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Example 1:
Input: [1,3,null,null,2]
1
/
3
2
Output: [3,1,null,null,2]
3
/
1
2
Example 2:
Input: [3,1,4,null,null,2]
3
/
1 4
/
2
Output: [2,1,4,null,null,3]
2
/
1 4
/
3
Follow up:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
My code:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
self.pre=TreeNode(-float('inf'))
self.swap1,self.swap2=TreeNode(0),TreeNode(-float('inf'))
self.travel(root)
self.swap1.val,self.swap2.val=self.swap2.val,self.swap1.val
def travel(self,x):
if not x:
return
self.travel(x.left)
if self.pre.val!=-float('inf') and self.pre.val>x.val:
self.swap1=x#Swap 1 will be the right most with value left larger than root
if self.swap2.val==-float('inf'): self.swap2=self.pre#Swap 2 will alwyas be the left most one invalid node
self.pre=x
self.travel(x.right)Solution: https://leetcode.com/problems/recover-binary-search-tree/