Home » Python » LeetCode Recover Binary Search

LeetCode Recover Binary Search

LeetCode Recover Binary Search Tree for solving problems


Original title

two nodes in a two fork search tree exchange positions to locate and adjust.


attention:



  • is better than using constant space


example:


input:


 3
/
1 2

output:


 2
/
1 3

Problem-solving thinking
In order traversal of

two binary search tree node can make it arranged in an ascending sequence, then the problem can be simplified to an increasing sequence has two elements swapped. While the front element is greater than elements after the error in order, if the entire sequence is such a problem that, as long as the exchange of these two elements, if there are two, while only two elements have order problems, should be before the first element of the exchange of dislocation (large elements should be put back after second) elements and dislocation (small element. put forward)
AC source code

#, Definition, for, a, binary, tree, node.
class TreeNode (object) :
def __init__ (self, x) :
Self.val = x
Self.left = None
Self.right = None
class Solution (object) :
def __init__ (self) :
Self.node1 = None
Self.node2 = None
Self.pre = None
def recoverTree (self, root) :
"""
: type, root:, TreeNode
: rtype:, void, Do, not, return, anything, modify, root, in-place, instead.
"" "
"
Self.__scan (root)
Self.node1.val, self.node2.val = self.node2.val, self.node1.val
def __scan (self, root) :
if root is None:
return
Self.__scan (root.left)
if, self.pre, is, not, None:
if root.val < self.pre.val:
if self.node1 is None:
Self.node1 = self.pre
Self.node2 = root
else:
Self.node2 = root
Self.pre = root
Self.__scan (root.right)
if __name__ = "__main__" :
None

welcome to my Github (https://github.com/gavinfish/LeetCode-Python) to obtain the relevant source code.


Latest