Two nodes in the binary search tree are incorrectly swapped .
Please... Without changing its structure , Restore the tree .
Input : [1,3,null,null,2]
1 / 3 \ 2
Output : [3,1,null,null,2]
3 / 1 \ 2
Input : [3,1,4,null,null,2]
3 / \ 1 4 / 2
Output : [2,1,4,null,null,3]
2 / \ 1 4 / 3
Advanced : Only constant storage space .
A binary search tree appears , It's usually associated with medial traversal . The traversal sequence of binary search tree is an array arranged in ascending order . And in this topic , It shows that only two nodes in the whole binary search tree are wrongly exchanged . therefore , We just need to find these two nodes and swap them .
First node , Is the first to traverse in the middle order, when the previous node is greater than the next node , Let's pick the previous node ,;
Second node , After the first node is found , The previous node is larger than the next node , We choose the next node ;
So you need to set three global variables , Update three variables in the process of recursion .
class Solution: def __init__(self): """ Three global variables ,firstNode Represents the first point that needs to be swapped secondNode Represents the second point where positions need to be exchanged preNode At any time to update """ self.firstNode = None self.secondNode = None self.preNode = TreeNode(float("-inf")) def recoverTree(self, root: TreeNode) -> None: """ Do not return anything, modify root in-place instead. """ if not root: return firstNode,secondNode = self.help(root) firstNode.val,secondNode.val = secondNode.val,firstNode.val # Exchange two values def help(self,root): if not root: return self.help(root.left) if self.firstNode == None and self.preNode.val >= root.val: # If firstNode It's empty , It means that we haven't found the first point to be exchanged , # If the former is greater than the latter , That means we found the first one . self.firstNode = self.preNode # Assign the previous node to firstNode if self.firstNode and self.preNode.val >= root.val: # The premise of finding the second node to be exchanged is that the first node to be exchanged has been found , namely firstNode Not empty self.secondNode = root # Assign the next node to secondNode self.preNode = root # to update preNode self.help(root.right) return self.firstNode,self.secondNode # Returns two nodes