https://leetcode.com/problems/recover-binary-search-tree


Timeout, 1917/1919


```python
from dataclasses import dataclass
from itertools import permutations, combinations


# Definition for a binary tree node.
"""
@dataclass
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""

class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        #2022/12/14 04:03
        def insert(root, value):
            if not root:
                return TreeNode(value)
            elif value < root.val:
                root.left = insert(root.left, value)
            else:
                root.right = insert(root.right, value)
            return root

        def left_to_right_travel(root):
            res = []
            if root:
                res = left_to_right_travel(root.left)
                res.append(root)
                res = res + left_to_right_travel(root.right)
            return res
        
        def left_to_right_travel_without_recursion(root):
            node_list = []
            queue = []
            node = root
            while len(queue) != 0 or node != None:
                if node:
                    queue.append(node)
                    node = node.left
                else:
                    node = queue.pop()
                    # do something with the node
                    #print(node.val)
                    node_list.append(node)
                    node = node.right
            return node_list

        self.it_is_binary_search_tree = True
        def verify_binary_search_tree(root):
            if self.it_is_binary_search_tree == False:
                return
            if root.left:
                verify_binary_search_tree(root.left)
                if root.left.val < root.val:
                    pass
                else:
                    self.it_is_binary_search_tree = False
                    return
            if root.right:
                verify_binary_search_tree(root.right)
                if root.val < root.right.val:
                    pass
                else:
                    self.it_is_binary_search_tree = False
                    return

        def search_one_value(root, value):
            while root != None:
                if value > root.val:
                    root = root.right
                elif value < root.val:
                    root = root.left
                else:
                    return True 
            return False

        # def is_binary_search_tree(node: TreeNode, floor: int, ceiling: int) -> bool:
        #     if not node: return True
            
        #     if not is_binary_search_tree(node.left, floor, node.val): return False
        #     if not (node.val > floor and node.val < ceiling): return False
        #     if not is_binary_search_tree(node.right, node.val, ceiling): return False
            
        #     return True

        def is_binary_search_tree(root):
            def is_bst(node, min, max):
                if node.val <= min:
                    return False
        
                if node.val >= max:
                    return False
        
                left_ok = True
                right_ok = True
        
                if node.left is not None:
                    left_ok = is_bst(node.left, min, node.val)
                if node.right is not None:
                    right_ok = is_bst(node.right, node.val, max)
        
                return left_ok and right_ok
        
            if root is None:
                return True
        
            return is_bst(root, float('-inf'), float('inf'))

        def find_wrong_nodes_with_root_node_value(root):
            wrong_node_list = []
            
            queue = []
            node = root.left
            while len(queue) != 0 or node != None:
                if node:
                    queue.append(node)
                    node = node.left
                else:
                    node = queue.pop()
                    # do something with the node
                    if node.val > root.val:
                        the_wrong_node_value = node.val
                        wrong_node_list.append(node)
                    node = node.right
            
            queue = []
            node = root.right
            while len(queue) != 0 or node != None:
                if node:
                    queue.append(node)
                    node = node.left
                else:
                    node = queue.pop()
                    # do something with the node
                    if node.val < root.val:
                        the_wrong_node_value = node.val
                        wrong_node_list.append(node)
                    node = node.right
            
            return wrong_node_list

        wrong_node_list = find_wrong_nodes_with_root_node_value(root)
        node_list = left_to_right_travel(root)
        #print(len(wrong_node_list))
        #print([node.val for node in wrong_node_list])
        if len(wrong_node_list) == 1:
            wrong_node_list[0].val, root.val = root.val, wrong_node_list[0].val
        else:
            value_list = [node.val for node in node_list]
            index_list = list(range(len(node_list)))
            possibility_list = combinations(index_list, 2)

            for one in possibility_list:
                new_value_list = value_list.copy()
                new_value_list[one[0]], new_value_list[one[1]] = new_value_list[one[1]], new_value_list[one[0]]
                for index, node in enumerate(node_list):
                    node.val = new_value_list[index]
                ok = True
                for node in node_list:
                    if not is_binary_search_tree(node):
                        ok = False
                        break
                if ok == True:
                    break
                #print(ok)
        #2022/12/14 10:08, time out, 1917/1919
```