Leetcode: restore binary search tree (Python)

A good function 2020-11-13 02:53:29
leetcode restore binary search tree

1. Title Description

Two nodes in the binary search tree are incorrectly swapped .

Please... Without changing its structure , Restore the tree .

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
``````

Advanced : Only constant storage space .

2. Ideas

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 .

Look for these two points

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 .

2.1 python Code

``````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
``````