【python/hard/99】Recover Binary Search Tree

タイトル
https://leetcode.com/problems/recover-binary-search-tree/description/リンクを開けて、今日はべたつくのがおっくうで、テーマは少し長いです
基本的な考え方
BST=="中序遍歴が秩序化されている誤操作された場合:BST=="中序遍歴は必ず秩序化されていないものが見つかればよい〜第1の乱序の数字はpreであり、第2の乱序の数字はrootであり、2つのポインタでそれぞれ保存し、値を交換すればよいので、木を完全に遍歴する必要はない.
時間複雑度O(n)空間複雑度O(1)

# 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.n1 = self.n2 = None
        self.prev = None
        self.findTwoNodes(root)
        self.n1.val,self.n2.val = self.n2.val,self.n1.val

    
    def findTwoNodes(self,root):
        if root:
            self.findTwoNodes(root.left)
            if self.prev and self.prev.val > root.val:
                if self.n1 == None:
                    self.n1 = self.prev
                self.n2 = root
            self.prev = root
            self.findTwoNodes(root.right)